Could anybody please check my proof about connected graph?

Question

I have written a proof of the following statement but not sure whether it is correct or not.

Let $G$ be a connected graph and each vertex has even degree. Show that if we remove ANY edge of the graph $G$, we still get a connected graph.

My work:

We know that if a graph is connected and each edge has even degree, then the graph is Eulerian. By the definition of Eulerian graph, there is a closed path that contains each edge of $G$ once. Let $v$ be an arbitrary vertex in $G$, we can start from $G$ and travels the Euler path in TWO ways and come back at $v$ again. But $G$ cannot have a vertex of degree $0$ otherwise it will be disconnected, so each vertex has minimum degree $2$. Hence if we remove any edge, we won't create an isolated vertex. From $v$ we can travel through a path that does not contain the removed edge, since each Euler path can be travelled in two ways, there is always a closed path that starts and ends at $v$. Therefore, the $G$ is still connected.

Could anybody please check my proof, if it is incomplete, could anybody please give me some advice how to correct and improve the proof? Or is there any better way to write the proof?

Thanks.

Answer 1

Perhaps this is just me being pedantic but the argument I think you're trying to make wasn't very clear to me upon the first reading. Is this what you mean?

Note that since every such graph has an Eularian cycle, there necessarily exist two paths for each vertex to every other vertex which have no edges in common. Thus removing any single edge cannot isolate any vertex from any other since the edge belongs to at most one of the paths connecting the two vertices.

Using Eulerian paths is certainly a clever approach regardless though!

Answer 2

Archaick has already given you a simple exposition of your correct approach. I would like to point out an interesting fact, which is that it is actually crucial to use the Eulerian property of $G$, which proceeds via the theorem that every finite graph with even vertex degrees has an Eulerian loop, and hence any two vertices are in some cycle.

The reason is that this is false for infinite graphs! Consider the graph formed by taking all integers as vertices and connecting each pair of adjacent integers with an edge. Clearly every vertex has even degree and the graph is connected. But removing any edge disconnects the graph! You can see that the proof of the given statement for finite graphs fails in this case because it isn't true that any pair of vertices are in some cycle (in fact not even one pair).