3.4 Vertex Degree

Vertex Degree

The degree of a vertex $v$ in the graph $G$ , denoted by $d_{G} (v)$ or just $d (v)$ (or sometimes $\deg (v)$ , as in the book), is the number of edges that are incident to $v$ (with loops counted twice, i.e. each loop on $v$ contributes 2 to $d (v)$ )

Theorem 3.1 Degree-sum Formula

If $G$ is a graph with vertices $v_{1}, v_{2}, \dots, v_{n}$ , then $\sum_{i = 1}^{n} d (v_{i}) = 2 | E (G) |$

Proof

Each loop contributes 2 to the summation. In the summation, each edge $e = u v$ that is not a loop is counted exactly twice, once in $d (u)$ and once in $d (v)$

Corollary 3.1

In any graph, the number of vertices of odd degree is even

Proof

Let $x_{1} \dots, x_{n}$ be vertices of graph $G$ with even degree and let $y_{1}, \dots, y_{m}$ be vertices of odd degree
Let $S = d (x_{1}) + \dots + d (x_{n})$
and $T = d (y_{1}) + \dots + d (y_{m})$
By Theorem 3.1, $S + T$ is even
Since $S$ is the sum of even numbers, $S$ is even
So $T$ must be even
Since $T$ is the sum of $m$ odd numbers, $m$ must be even

Friendship Puzzle

At any party of two or more people, show that there are always two people with exactly the same number of friends at the party

Proof

Let $G$ be a simple graph with vertex set $V (G) = {v_{1}, \dots, v_{n}}$ denoting people at the party
Edges of $G$ are defined as follows: $u v \in E (G)$ if $u$ and $v$ are friends
For $i = 1, \dots, n, d (v_{i}) =$ number of friends of $v_{i}$

Consider the following 2 cases

Case 1: Everyone at the party has at least one friend at the party
So for every $i = 1, \dots, n, 1 \leq d (v_{i}) \leq n - 1$
Since $n$ variables $d (v_{1}), \dots, d (v_{n})$ are each assigned one of $n - 1$ numbers from the set ${1, \dots, n - 1}$ , at least two of them must have the same value (Pigeonhole Principle)

Case 2: Someone at the party does not have any friends at the party
For some $i \in {1, \dots, n}, d (v_{i}) = 0$
So for every $i = 1, \dots, n, 0 \leq d (v_{i}) \leq n - 2$
Since $n$ variables $d (v_{1}), \dots, d (v_{n})$ are each assigned one of $n - 1$ numbers from the set ${0, \dots, n - 2}$ , at least two of the must have the same value (Pigeonhole Principle)