7
$\begingroup$

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.

  • 0
    let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/2828/discussion-between-samrat-roy-and-didier-piau)2012-03-19

5 Answers 5

0

Here exactly two vertices exist , but the degree of the vertices are odd. In this situation the odd degree are 1 or 3 in two vertices.In the undirected graph degree one have exactly connection between two vertex. In the case of 3 vertices both vertex have a loop (the loop consider as degree two in undirected graph) and a connected path between them. There fore exactly two vertices of odd degree then there is a path between them.

15

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$.

4

"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."

  • 0
    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 ?2012-03-19
1

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$).