mathschallenge.net logo

Odd Vertices

Problem

A graph consists of vertices and edges. The order of a vertex is defined to be the number of connected edges. For example, in the graph below the order of each vertex is identified.


It can be seen that there are two odd vertices and three even vertices.

Prove that in any graph there will always be an even number of odd vertices.


Solution

Let us suppose that we already have a graph for which there are an even number of odd vertices.

First we note that adding an unconnected vertex does no change the order of any existing vertex, and as the new vertex will have order zero, we do not change the number of odd vertices in the graph.

However, if we add a new edge it must connect between two existing vertices and there are precisely three possibilities depending on the current order of the two vertices it will be connected to:

  1. If they both have an even order the new edge will make them both odd, increasing the number of odd vertices by two.
  2. If they are both odd the new edge will make them both even, reducing the number of odd vertices by two.
  3. If one is odd and the other is even the new edge will make one vertex odd and the other even, not changing the total number of odd vertices.

Whichever way we can see that IF the graph had an even number of odd vertices before we added the new edge it will have an even number after we add it.

It should be clear that all graphs can be created by starting with a collection of unconnected vertices and then adding the edges one at a time.

As a collection of unconnected vertices each have order zero, the graph satisfies the requirement that there be an even number of odd vertices.

We have just shown that adding new edges will not violate this balance. Hence we prove inductively that all graphs have an even number of odd vertices.

Problem ID: 254 (12 Dec 2005)     Difficulty: 3 Star

Only Show Problem