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

anthmoo · #1 $Old$ January 14th, 2007, 03:48 AM

How would I go about explaining this please?

Thanks guys!

ThePerfectHacker · #2 $Old$ January 14th, 2007, 08:54 AM

Quote:

Originally Posted by anthmoo $View Post$

How would I go about explaining this please?

Becuase the sum of the edge is a formula,
$2|E|=\sum_{v\in V}d(v)$
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.

anthmoo · #3 $Old$ January 14th, 2007, 09:48 AM

Quote:

Originally Posted by ThePerfectHacker $View Post$

Becuase the sum of the edge is a formula,
$2|E|=\sum_{v\in V}d(v)$
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.

Plato · #4 $Old$ January 14th, 2007, 11:01 AM

Quote:

Originally Posted by anthmoo $View Post$

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.

Soroban · #5 $Old$ January 14th, 2007, 03:21 PM

Hello, anthmoo!

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

Quote:

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

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

Now add another vertex $X$ to the graph.

If $X$ is not connected to any of the $n$ 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 $X$ is connected to any of the $n$ vertices, there are two outcomes.

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

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

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

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

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

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

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

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

Plato · #6 $Old$ January 14th, 2007, 03:55 PM

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.