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