Combinatorics • Topic 27

Degree of a Vertex

The degree of a vertex is a local property that often forces global structure.

Definition

Definition (Degree)

The degree of a vertex

v

, denoted

de g (v)

, is the number of edges incident to

v

Isolated Vertex: $de g (v) = 0$ .
Leaf: $de g (v) = 1$ .
Regular Graph: All vertices have the same degree $k$ ( $k$ -regular).

Extremal Principles

Look at the vertex with the minimum or maximum degree.

Example

Prove that in any simple graph with

n \geq 2

vertices, there are at least two vertices with the same degree.

Proof. Possible degrees are ${0, 1, \dots, n - 1}$ . However, a graph cannot have both a vertex of degree 0 (connected to no one) and a vertex of degree $n - 1$ (connected to everyone else). So the set of realized degrees is a subset of size at most $n - 1$ from ${0, \dots, n - 1}$ . By Pigeonhole Principle, two vertices share a degree. ∎

Practice Problems

Exercise (Problem 1)

If a graph has

n

vertices and every vertex has degree

k

, how many edges does it have?

Exercise (Problem 2)

Prove that if every vertex has degree

\geq 2

, the graph contains a cycle.

Exercise (Problem 3)

Let

G

be a graph with

n

vertices and minimum degree

δ \geq (n - 1) /2

. Prove

G

is connected.