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

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