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

Question

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.

Answer 1

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.

Answer 2

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.