# A finite graph with exactly two vertices with odd degree must have a path joining them.

I would really appreciate it if anyone would validate if my argument ( proof ? ) for the above statement is valid. I am aware of other proofs but the current argument is more of a task in rational/logical thinking and mathematical writing style.

I am aware this is a open ended question but I would also like it if people would comment on my style so that I can improve on it.

Let $G$ be a disconnected finite graph with exactly two vertices, $u$ and $v$, with odd degrees and two components. Suppose that $u$ and $v$ belong to different components of $G$.

Then either of the two possibilities given below must hold such that number of edges in $G$ is a positive integer.

1) There exists at least one other vertex with odd degree in each component of $G$ such that the number of edges in each component is a positive integer. A contradiction with our assumption that $G$ has exactly two vertices with odd degree.

2) There exists an edge joining the two components. Another contradiction, as we have said previously that $G$ is disconnected.

-
There is no path from 1 to 4 in the graph with four vertices 1, 2, 3 and 4 and two edges {1,2} and {3,4}. –  Did Mar 19 '12 at 9:15
That graph does not have exactly two vertices of odd degree. –  JeffE Mar 19 '12 at 9:28
It is a finite graph with at least two vertices of odd degree, which is the hypothesis you have given in the title. –  Gerry Myerson Mar 19 '12 at 9:36
My comment above addressed the first version of the title. On the positive side, the title is now modified. On the negative side, no reaction from the OP to acknowledge there was a problem (except a quite irrelevant comment, now deleted). –  Did Mar 19 '12 at 9:53
Deleted last comment as Didier Piau counter example was indeed correct with respect to the last title. –  Samrat Roy Mar 19 '12 at 9:53

"Let $G$ be a disconnected finite graph...." Why? The proof should start with "If $G$ is connected, then of course there's a path between any two vertices, so assume $G$ is a disconnected finite graph...."

"...with exactly two vertices ... with odd degrees..." Why? You are trying to prove something about graphs with at least two vertices of odd degree, not exactly two vertices of odd degree. And why two components? I think it should go, "...with at least two vertices, $u$ and $v$, of odd degree."

"Then either of the two possibilities given below must hold such that [the] number of edges in $G$ is a positive integer." This is not English. The clause beginning "such that" doesn't make sense. What are you trying to say?

You give no reason why one of the two possibilities must hold. You write ungrammatical sentences (the two sentences with the word, "contradiction", are not grammatically correct).

On top of this, there is Didier's objection that what you are trying to prove is false. Maybe you really do want the hypothesis to state "exactly" instead of "at least". Or maybe you want the conclusion to be "a path joining some pair of vertices of odd degree."

-
Thank you for your comments! I have corrected the title as it was indeed misleading. May I ask if it would be best to edit the text or append the new text as an answer ? –  Samrat Roy Mar 19 '12 at 9:52

Assume $G$ is a finite graph with exactly $2$ vertices of odd degree, call them $u$ and $v$. If $G$ is connected, then we are finished. Thus we can assume $G$ is disconnected. Let $J$ be the connected component of $G$ such that $u\in J$. Since $J$ is a graph, it must contain an even number of vertices of odd degree since

$$\sum_{w\in V(J)} \text{deg}(w)=2|E(J)|.$$

Thus there is at least one more vertice of odd degree in $J$. Since $G$ contains exactly two vertices of odd degree, we must have $v\in J$. This implies there is a path from $u$ to $v$.

-
Let $G$ be a graph with exactly $2$ vertices of odd degree $u$ and $v$.
• If $G$ has a cycle ($C_n$ for $n \geq 3$), then delete it (this preserves the parity of the vertex degrees). Repeat until $G$ is a forest.
• Since $G$ is a forest, $G$ is a path from $u$ to $v$, along with some isolated vertices (as any other forest will have another vertex of degree $1$).