# $G$ has exactly $n-1$ edges implies every edge of $G$ is a bridge

Let $G$ be a connected simple graph on $n$ vertices. Show that $G$ has exactly $n-1$ edges implies every edge of $G$ is a bridge.

The above statement is obviously true. Some textbooks even use this statements as the definition of a tree. However, my teacher suggests us to prove it directly as an exercise. It would be great if you can verify my proof below and/or give another direct proof of the statement.

We proceed by induction on $n$, the number of vertices of $G$. For the case $n=2$, $G$ has 2 vertices and 1 edge. It is clear that this edge is a bridge.

Assume $G$ has $n$ vertices and exactly $n-1$ edges. We claim that there must exist a vertex $v$ with $\text{deg}(v)=1$. If the claim is not correct, then $$n-1 = \text{number of edges} = \frac{1}{2} \times \text{sum of degree} \geq \frac{1}{2} \times 2n=n$$ which is a contradiction. Hence, such $v$ exists, with only one edge $\alpha$ incident to it. Now, on the removal of $\alpha$, $G$ is partitioned into two connected component $G_1$ and $G_2$. In particular, $G_1=\{v\}$ is a singleton. Hence, $\alpha$ is a bridge. By induction hypothesis, $G_2$ has $n-1$ vertices and exactly $n-2$ edges, thus every edge in $G_2$ is a bridge. Hence, every edge in $G$ is a bridge.

Wrong version:

We proceed by induction on $n$, the number of vertices of $G$. For the case $n=2$, $G$ has 2 vertices and 1 edge. It is clear that this edge is a bridge.

Assume that $G$ has $n-1$ vertices and exactly $n-2$ edges. By the induction hypothesis, these $n-2$ edges are bridges. Now, we choose an arbitrary vertex in G, join it to a newly-added vertex $v$ by an edge $\alpha$. It remains to show $\alpha$ is a bridge. Note that, on the removal of $\alpha$, the graph will become disconnected as there will be no edge incident to $v$. Hence, $\alpha$ is indeed a bridge and we are done.

• You haven't told us what $G$ is, nor any assumptions about $G$ (for example, presumably it is supposed to be connected,) nor what a bridge is. (I've never encountered the term, although I can guess what it means in context here.) Basically, you just start out this question assuming we all know what you are talking about. Help people help you. – Thomas Andrews Nov 30 '15 at 16:53
• Sorry that I haven't included a detailed version of the statement. It is now amended. – Nighty Nov 30 '15 at 16:56
• That proof looks correct to me. – Eric Naslund Nov 30 '15 at 17:00
• One problem I see with this proof is that you assume that every $n - 1$ edges graph can be obtained in the way you describe. Suppose I give you a graph $G$ with $n$ vertices and $n - 1$ edges, and you can't find the $v$ and $\alpha$ you describe. Then you can't use the induction hypothesis on $G - v$ as you are (implicitly) doing. In fact, you need $G$ to always a vertex $v$ with one incident edge. – Manuel Lafond Nov 30 '15 at 17:08
• Yes, you haven't shown that this is true for any $G$ with $n$ vertices, only for $G$ which can result by adding a vertex and edge to a graph with $n-1$ vertices. In general, you need to start with a graph $G$ with $n$ vertices, and reduce it to a graph with $n-1$ vertices. – Thomas Andrews Nov 30 '15 at 17:17

Suppose $G=(V,E)$ is a connected Graph with $|V|=n$ and $|E|=n-1$ and $G$ has at least one edge $e_B$ that is not a bridge. We know that an edge is a bridge if and only if it is not contained in a cycle. Since $e_B$ is a bridge, $e_B$ has to be part of a cycle between some vertices $V_1=\{v_1,...,v_k\}$. It follows that these vertices have to be connected with at least $k$ edges.
Now we look at the $n-k$ remaining vertices $V_2=\{v_{k+1},...,v_n\}$. Since $k$ edges are part of the cycle descibed above and only connect some vertices of $V_1$, there can not be more than $|E|-k=n-k-1$ edges which connect between vertices of $V_2$.
We know that at least $m-1$ edges are required to connect $m$ vertices. $n-k-1$ edges and $n-k$ vertices are not part of the cycle, but because at least one vertex of $V_2$ has to be connected to one vertex of $V_1$ (because if not, $G$ wouldn't be connected), at least $n-k-1+1=n-k$ edges not part of the cycle would be required for $G$ to be connected. Therefore, $G$ can not be connected. $\square$