Thread: Explain why, in ANY graph, there must be an even number of odd vertices...

How would I go about explaining this please?

Thanks guys!

Originally Posted by anthmoo

How would I go about explaining this please?

Becuase the sum of the edge is a formula,

The summation formula means the sum of all degrees of verticies.
Sine the left hand side is even thus is the right.
Thus, the sum of all degrees is always even.

Originally Posted by ThePerfectHacker

Becuase the sum of the edge is a formula,

The summation formula means the sum of all degrees of verticies.
Sine the left hand side is even thus is the right.
Thus, the sum of all degrees is always even.

All degrees? I was just asking about the sum of degrees of odd nodes, not the sum off all degrees of nodes.

Originally Posted by anthmoo

All degrees? I was just asking about the sum of degrees of odd nodes, not the sum off all degrees of nodes.

If one adds any collection of integers and the resulting sum is even then that collection must contain an even number of odd integers.

Hello, anthmoo!

Here is a primitive approach . . . almost an inductive proof.

Explain why, in ANY graph, there must be an even number of odd vertices.

Let's say we have a graph with vertices (some even, some odd)
. . and the parity (evenness or oddness) of each vertex is noted.
Let's say that there are even vertices and odd vertices.


Now add another vertex to the graph.

If is not connected to any of the vertices,
. . it remains a 0-vertex (even).
The number of even vertices increases by one,
. . but the number of odd vertices does not change.


If is connected to any of the vertices, there are two outcomes.

(a) is connected to an even vertex.
. . . Then becomes an odd vertex and the even vertex becomes odd.
. . . The number of odd vertices increases by two; its parity does not change.

(b) is connected to an odd vertex.
. . . Then becomes odd and the odd vertex becomes even.
. . . The number of odd vertices does not change.


Continue to connect (or not connect) to other vertices.

If is an even vertex, we have covered the results in (a) and (b) above.

If is an odd vertex, connecting it to another vertex makes even.
. . The vertex is connected to will change from even-to-odd or odd-to-even.
In both cases, the evenness or oddness of is unchanged.


Bottom line: adding a vertex does not change the parity of .


Let's begin with the simplest graph: one vertex.
. . It is a 0-vertex, so there is one even vertex: .
. . There are no odd vertices, so: , an even number.

We have shown above that adding vertices does not change the parity of .
No matter how many vertices are added and how they are connected to existing vertices,
. . the number of odd vertices will remain even.

The proof of the theorem that TPH quoted is so elegant. It works for any graph.
The sum of the degrees of the vertices of a graph equals twice the number of edges.
This is call the ‘Handshaking Theorem’ is modern texts, but it is due to Euler.
Proof:
By adding the all the degrees of the vertices involves the question “How many times does each edge get counted?” Each edge involves two vertices (even loops by definitions). Thus each edge is counted twice.