Prove that every connected graph of all whose vertices have even degree contain no bridges.

I tried to prove this by induction. So let $G$ be a connected graph of order $n$. Since all vertices of $G$ have even degree, $n \geq 3$.

Base $n=3$ we have $C_3$, so every edges lie on a cycle thus, non of those edges can be bridge.

Assume that this is true for $n=k$, let $h$ be a graph obtained by adding 2 vertex $a,b$ to $G$ and joining $a,b$ to every vertex in $G$ so that every vertex in $G$ still have even degree. Since the statement is true for $n=k$, $G$ has no bridge, meaning very edge of $G$ lie in some cycle. Now when we add some edge $e_{a_1},e_{a_2},..., e_{a_k}$ from $a$ to $u \in V(G)$ and $e_{b_1},e_{b_2},..., e_{b_k}$ from $b$ to $u$, we just form some new cycle, and these edges lie on those new cycle. So non of these edges can be bridge, so $H$ contain no bridge. By induction, this statement is true.

Is my reasoning ok? I still feel a little bit awkward on $H$ contain no bridge part.

  • $\begingroup$ The induction does not hold: $H$ is not every graph with $n+2$ nodes and even degree.. $\endgroup$ – Exodd Sep 27 '14 at 13:29

It's a little easier:

If $G$ contains a bridge, call $H$ one of the two subgraph in which the graph is divided by the bridge.

The sum of the degrees of all the nodes in $H$ is equal to 2 times the number of edges in $H$, so it's an even number. But all the nodes in it have even degree, except for the node from which the edge departed, that has odd degree, so we have an absurdity.

  • $\begingroup$ what is an even number? the sum of degree? the sum of degree is always even. You are trying to do a proof by contradiction? $\endgroup$ – Diane Vanderwaif Sep 27 '14 at 17:26
  • $\begingroup$ exactly: the sum of the degree is always even, but if $G$ contains a bridge, then it can't be even $\endgroup$ – Exodd Sep 27 '14 at 17:28
  • $\begingroup$ so you said, the node from which the edge departed, you mean the cut-vertex, and the cut vertex has to have odd degree? $\endgroup$ – Diane Vanderwaif Sep 27 '14 at 17:34
  • $\begingroup$ I'm considering only one of the two parts of the graph you obtain deleting the bridge. In it every node has even degree, except for the cut vertex $\endgroup$ – Exodd Sep 27 '14 at 17:36

I understand your Question Like this.

Consider a graph G(V,E) with all the vertices having even degree. Prove that the G would not have a bridge.

The reasoning is very simple. There is already a theorem stating "Every graph with all even degree vertices have an Eulerian circuit". This means that if the graph as you said contained a bridge then it means we will not have an Eulerian circuit contradicting the theorem stated above.

Hope I make sense.


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.