That's tricky!

Probability Level 3

For a simple graph $G$ with at least two vertices, which of the following statements must be true?

Graph is called simple if it doesn't contain multiple edges between the same pair of nodes and no vertex has self-edges.

Note : The degree of a vertex is the number of connections it has.

The number of vertices with even degree is even. The number of vertices with odd degree is even. The number of vertices with odd degree is odd. The number of vertices with even degree is odd.

1 solution

Sam Bealing
Jul 24, 2016

Each edge connects $2$ vertices so increases the sum of the degrees of the vertices by $2$ . It therfore follows that the overall number of degrees is even and so there must be an even number of odd vertices (otherwise the sum of degrees would be odd).

That's tricky!

1 solution

0 pending reports