1
$\begingroup$

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.


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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Thomas Andrews Nov 30 '15 at 16:53
  • $\begingroup$ Sorry that I haven't included a detailed version of the statement. It is now amended. $\endgroup$ – Nighty Nov 30 '15 at 16:56
  • $\begingroup$ That proof looks correct to me. $\endgroup$ – Eric Naslund Nov 30 '15 at 17:00
  • 1
    $\begingroup$ 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. $\endgroup$ – Manuel Lafond Nov 30 '15 at 17:08
  • $\begingroup$ 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. $\endgroup$ – Thomas Andrews Nov 30 '15 at 17:17
1
$\begingroup$

Another proof by contradiction would be:

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$

I had some trouble to express my thoughts, so please feel free to comment if something isn't clear.

$\endgroup$
  • $\begingroup$ direct proof by contradiction? $\endgroup$ – Jorge Fernández Hidalgo Dec 1 '15 at 4:01
  • $\begingroup$ Yeah I too noticed that this is kind of nonsensical wording :D $\endgroup$ – thegentlecat Dec 1 '15 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.