How would I go about explaining this please?

Thanks guys!

- Jan 14th 2007, 02:48 AManthmooExplain why, in ANY graph, there must be an even number of odd vertices...
How would I go about explaining this please?

Thanks guys! - Jan 14th 2007, 07:54 AMThePerfectHacker
- Jan 14th 2007, 08:48 AManthmoo
- Jan 14th 2007, 10:01 AMPlato
- Jan 14th 2007, 02:21 PMSoroban
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 $\displaystyle n$ vertices (some even, some odd)

. . and the parity (evenness or oddness) of each vertex is noted.

Let's say that there are $\displaystyle E$ even vertices and $\displaystyle O$ odd vertices.

Now add another vertex $\displaystyle X$ to the graph.

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

(a) $\displaystyle X$ is connected to an even vertex.

. . . Then $\displaystyle 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) $\displaystyle X$ is connected to an odd vertex.

. . . Then $\displaystyle X$ becomes odd and the odd vertex becomes even.

. . . The number of odd vertices does not change.

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

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

If $\displaystyle X$ is an odd vertex, connecting it to another vertex makes $\displaystyle X$ even.

. . The vertex $\displaystyle X$ is connected to will change from even-to-odd or odd-to-even.

In both cases, the evenness or oddness of $\displaystyle O$ is unchanged.

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

Let's begin with the simplest graph: one vertex.

. . It is a 0-vertex, so there is one even vertex: $\displaystyle E = 1$.

. . There are no odd vertices, so: $\displaystyle O = 0$, an even number.

We have shown above that adding vertices does not change the parity of $\displaystyle O$.

No matter how many vertices are added and how they are connected to existing vertices,

. . the number of odd vertices will remain even.

- Jan 14th 2007, 02:55 PMPlato
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.