[Math] Prove that in a simple graph there is a path from any odd vertex to any odd vertex

graph theory

Let $k$ be the number of vertices.

If $k = 1$, then the point is isolated and therefore has degree 0; WLOG, we can assume that no point is isolated.

With $k = 2$, there is a vertex of degree 1 to another vertex of degree 1.

With $k = 3$, suppose the graph is connected. Then 3 vertices have degree 2, and removing one edge leads to two vertices with one less degree – so the degree sequence would be [1,2,1], satisfying the hypothesis.

WLOG we can assume if $k$ is odd then the graph is not connected. Then the graph has at least one connected component. For any $k = n$ the endpoints of these connected components have degree 1.

If the graph is connected and has an even number of vertices then the vertices have degree (n-1), which is odd. QED.

Is there anything I am missing from my proof? I don't see the need to prove the case for even number of vertices with a graph that is not connected, so I didn't write it out. Also, could my proof be made more concise? Are there any errors?

Best Answer

You seem to be proving the wrong result. In this setting, there are two cases:

  • All odd-degree vertices belong to the same connected component. In this case, there is, by definition, a path from any odd-degree vertex to any other odd-degree vertex.

  • Two odd degree vertices belong to disjoint components. In this case, there are, by definition, two odd-degree vertices for which there is no path connecting them. And this situation can occur: just take the disjoint union of any two graphs each with an odd degree vertex.

    For example, there is no path connecting the two pink vertices below:

    enter image description here

This means you're either attempting to prove something that is true by definition, or you're attempting to prove something that is false.

I suspect the correct task is to prove:

Given a connected graph with exactly two odd-degree vertices $u$ and $v$, there is an Eulerian trail from $u$ to $v$.

Since I have been asked to "Please take care in reading my proof.":

WLOG we can assume if k is odd then the graph is not connected.

Here's a connected $5$-vertex graph counterexample:

enter image description here

Then the graph has at least one connected component.

All graphs with at least $1$ vertex have at least one connected component.

For any k=n the endpoints of these connected components have degree 1.

Many graphs don't have "endpoints", i.e., leaf vertices (such as the one below).

If the graph is connected and has an even number of vertices then the vertices have degree (n-1), which is odd.

Here's a counterexample to this claim:

enter image description here

In fact, any connected subgraph of $K_n$, except $K_n$ itself, would be a counterexample.

Related Question