0
$\begingroup$

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.

3 Answers 3

3

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.

2

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.

1

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...