I know how to prove it when the degree of all vertices is 2. For larger even numbers i don't know if my proof works.
Here is my proof by contradiction:
Assume we have G = (V,E) with d(v) = 2 for all vertices, and e is a bridge of that graph.
Let us call the vertices of e, u and v.
If e is a bridge, G – e has 2 connected components with all vertices of degree 2 except u and v.
Take u and move to the only vertex that is adjacent to it u2. This vertex has only one non-visited neighbour u3. Similarly, ui has only one unvisited neighbour ui+1. Moreover, we can never go back to a visited vertex (since that would make it of degree 3) and neigther to the first one (u) which is of degree 1.
Therefore, since the set of vertices is finite, the only possible way to end our path, is to reach v, the only unvisited vertex of degree 1. Meaning that we have to move from one connected component to the other and thereby the graph is still connected and e is not a bridge as we assumed.
I know, the formalisation of the proof is not good and I would like to improve that too, but first of all, I would like to understand a proof for any n even, and not all vertices having the same degree just some that is even.
Thanks a lot, and have a nice day!
Best Answer
A connected graph where each vertex has even degree has a Euler circuit. It is now clear that the graph cannot contain a bridge: the existance of a Euler circuit implies that each two vertices are connected by at least two disjoint paths, meaning that deleting one edge cannot disconnect the graph.
Actually, your attempt at solving the problem can be reformulated to a proof showing that a connected graph where each vertex has even degree indeed has a Euler circuit: it must contain a cycle by your reasoning. Since each vertex in the remaining graph still has even degree, the edge set of the graph can be partitioned in cycles. These cycles can be connected to form a Euler circuit since the graph is connected.