Hi, I'm very new to graph theory and have a question.
For each positive integer $k$, what is the largest number of bridges in any $k$-vertex graph?
Thanks.
Hi, I'm very new to graph theory and have a question.
For each positive integer $k$, what is the largest number of bridges in any $k$-vertex graph?
Thanks.
Hint: In a tree, all edges are bridges. And removing an edge from a cycle of a graph containing a cycle, will not decrease the number of bridges.
HINT: Removing a bridge increases the number of components by $1$; what is the largest possible number of components of a graph with $k$ vertices? And if you start with just one component, how many increases of $1$ does it take to reach that largest possible number?
Once you’ve got that, you’ll want an example that actually has the largest possible number of bridges; a very simple graph will do the trick.
Just thinking out loud here: but what if the graph is just defined by a "straight line" of vertices and edges? Then each edge would be a bridge. I think this concept is a bit related to the definition of trees. If this is on the right track, then the answer seems quite obvious. The harder part would be to prove this...