Discrete Mathematics and Proof

Degree, the handshake lemma and complete graphs

Every link in a network has two ends. What does that one fact force on the number of links at each point, and which lists of link counts can a network actually have?

Unlocks

Graph isomorphism: when two drawings are the same graphDiscrete Mathematics and Proof Planar graphs and Euler's formulaDiscrete Mathematics and Proof Euler paths and circuitsDiscrete Mathematics and Proof

Where you are 4 in Graphs, vertices and edges

Logic, proof and discrete math6

Introductory graph theory10

Graphs, vertices and edges4

Degree, the handshake lemma and complete graphs

Weighted and directed graphs Graph isomorphism: when two drawings are the same graph Adjacency matrices and their powers

Why this exists

Computers joined by cables, people who know each other, cities joined by flights: each is a set of points with some pairs linked. Graphs are the language for all of them. The first number to ask about a point is how many links meet there, its degree. Degrees are local, one point at a time, yet they add up to a fact about the whole network: every link has two ends, so the degrees always sum to twice the number of links. That one count rules out plans before anyone builds them, and it starts the question of which lists of degrees a network can have at all.

Definition

This lesson takes two days. Day 1 is degree, the handshake lemma, complete graphs and regular graphs (Examples 1 to 4). Day 2 is degree sequences, complements and degree bounds (Examples 5 to 7).

A graph G = (V, E) is a finite nonempty set V of vertices together with a set E of edges, each edge an unordered pair \{u, v\} of two different vertices. The edge \{u, v\} is written uv; uv and vu are the same edge. Its two vertices are its endpoints, and they are adjacent, or neighbors. A drawing shows each vertex as a dot and each edge as a line between its endpoints; where two lines cross in a drawing there is no vertex unless a dot is drawn. The number of vertices is \lvert V \rvert and the number of edges \lvert E \rvert.

Because an edge is a set of two different vertices, no vertex is joined to itself (no loops), and because E is a set, no pair is joined twice (no repeated edges). Graphs with both properties are called simple, and every graph in this lesson is simple. A multigraph allows loops and repeated edges; some later problems need one.

The degree of a vertex v, written \deg(v), is the number of edges with v as an endpoint, which is also the number of neighbors of v. A vertex of degree 0 is isolated.
\delta(G) and \Delta(G) are the smallest and largest degrees of the vertices of G.
The complete graph K_n has n vertices and every pair of them as an edge.
A graph is r-regular if every vertex has degree r.
The degree sequence of G is the list of the degrees of its vertices, written from largest to smallest. A list of integers is graphic if it is the degree sequence of some simple graph.
The complement \overline{G} has the same vertices as G, and uv is an edge of \overline{G} exactly when u \ne v and uv is not an edge of G.

Intuition

Figure 1Seven computers and seven cables. The degrees are 3, 2, 3, 3, 2, 1, 0 for A to G.

Think of each edge as a cable with a plug at each end, and of the degree of a computer as the number of plugs in its back panel. Counting plugs computer by computer adds up the degrees. Counting plugs cable by cable gives two per cable. Same plugs, so the degree sum is twice the number of cables. In Figure 1 the degrees add to 3 + 2 + 3 + 3 + 2 + 1 + 0 = 14, and there are 7 cables.

Figure 2In K_n every vertex is joined to the other n - 1, and there are \displaystyle \frac{n(n-1)}{2} edges.

A complete graph is the network where every pair is cabled directly. Each of the n computers then has n - 1 plugs, n(n - 1) plugs in all, and two plugs per cable gives \displaystyle \frac{n(n-1)}{2} cables.

Results

1. The handshake lemma. In every graph G = (V, E),

\sum_{v \in V} \deg(v) = 2\lvert E \rvert.

2. Odd vertices come in pairs. In every graph the number of vertices of odd degree is even.

3. Complete graphs. Every vertex of K_n has degree n - 1, and K_n has \displaystyle \frac{n(n-1)}{2} = \binom{n}{2} edges.

4. Regular graphs. An r-regular graph on n vertices has \displaystyle \frac{rn}{2} edges, so rn is even.

5. Degree bounds. In a graph with n vertices, every degree is between 0 and n - 1, and n\,\delta(G) \le 2\lvert E \rvert \le n\,\Delta(G).

6. Complements. If G has n vertices, then \deg_{\overline{G}}(v) = n - 1 - \deg_G(v) for every vertex v, and G and \overline{G} together have \binom{n}{2} edges. So a list (d_1, \ldots, d_n) is graphic exactly when (n - 1 - d_n, \ldots, n - 1 - d_1) is.

7. A shared degree. Every graph with at least two vertices has two vertices of the same degree.

8. The removal test (Havel and Hakimi). Let d_1 \ge d_2 \ge \cdots \ge d_n be nonnegative integers with n \ge 2. The list is graphic exactly when d_1 \le n - 1 and the list of n - 1 numbers

d_2 - 1,\ \ldots,\ d_{d_1 + 1} - 1,\ d_{d_1 + 2},\ \ldots,\ d_n

is graphic: delete the largest entry d_1 and lower the next d_1 entries by 1. Repeating, re-sorting each time, ends either at a list of zeros (graphic: isolated vertices) or at a negative entry or an entry too large for the list’s length (not graphic).

Why it is true

Result 1. Proof. Count the pairs (v, e) in which v is an endpoint of the edge e. Sorted by vertex, v is in \deg(v) pairs, so there are \sum_v \deg(v) pairs. Sorted by edge, each edge has exactly two endpoints, so there are 2\lvert E \rvert pairs. These count one set, so they are equal. \square This is counting pairs two ways from Combinatorial proof: counting one set two ways, whose Day 1 set the graph case aside for here.

Result 2. Proof. Split the degree sum into the sum over even-degree vertices and the sum over odd-degree vertices. The total is even by Result 1, and the first part is even, so the second part is even. A sum of odd numbers is even only when there is an even number of them (Proving statements about even and odd numbers). \square

Result 3. Each vertex of K_n is joined to all n - 1 others. By Result 1, 2\lvert E \rvert = n(n - 1). Equally, each edge is a choice of 2 of the n vertices (Combinations).

Result 4. By Result 1, 2\lvert E \rvert = rn.

Result 5. A vertex’s neighbors are among the other n - 1 vertices. Each of the n terms of the degree sum lies between \delta(G) and \Delta(G); apply Result 1.

Result 6. Each of the n - 1 other vertices is a neighbor of v in exactly one of G and \overline{G}. Each of the \binom{n}{2} pairs is an edge of exactly one of them. A graph with the first list has a complement with the second, and the other way round.

Result 7. Proof. The degrees lie in 0, 1, \ldots, n - 1. A vertex of degree n - 1 is adjacent to every other vertex, so no vertex has degree 0 when one has degree n - 1. The n degrees therefore take at most n - 1 values, and by the pigeonhole principle two are equal. \square This is the party argument of The pigeonhole principle, Example 6, with guests as vertices and acquaintance as edges.

Result 8. Proof. Write d' for the shorter list. If d' is graphic, take a graph with degrees d' on vertices v_2, \ldots, v_n, where v_i has degree d'_i, add a new vertex v_1, and join it to v_2, \ldots, v_{d_1 + 1}. Those d_1 vertices gain 1 each, v_1 has degree d_1, and the degrees are the original list.

Now suppose the original list is graphic, with d_1 \le n - 1. Among all graphs on v_1, \ldots, v_n with \deg(v_i) = d_i, choose one in which v_1 has as many neighbors as possible among v_2, \ldots, v_{d_1 + 1}. Suppose, for contradiction, that some v_i with 2 \le i \le d_1 + 1 is not adjacent to v_1. Since v_1 has d_1 neighbors, some v_j with j > d_1 + 1 is adjacent to v_1, and d_i \ge d_j. Let a be 1 if v_i v_j is an edge and 0 if not. Then v_i has d_i - a neighbors other than v_j, while v_j has d_j - 1 - a neighbors other than v_1 and v_i, fewer. So some neighbor w of v_i, with w \ne v_j, is not adjacent to v_j; and w \ne v_1 because v_1 v_i is not an edge. Remove the edges v_1 v_j and v_i w, and add v_1 v_i and v_j w. Every degree is unchanged, and v_1 has one more neighbor among v_2, \ldots, v_{d_1 + 1}, against the choice of graph. So v_1 is adjacent to exactly v_2, \ldots, v_{d_1 + 1}, and deleting v_1 leaves a graph with degrees d'. \square

Worked examples

Example 1

Day 1: degrees in a small network

Senna is wiring an office. Figure 1 shows the computers A to G and the cables between them. Find every degree, check the handshake lemma, and check Result 2.

Solution

The degree of a vertex is its number of edges. A meets AB, AC, AD, so \deg(A) = 3. In the same way \deg(B) = 2, \deg(C) = 3, \deg(D) = 3, \deg(E) = 2, \deg(F) = 1, and G is isolated, \deg(G) = 0.

The sum is 3 + 2 + 3 + 3 + 2 + 1 + 0 = 14 = 2 \cdot 7, and there are 7 edges, as the lemma says. The odd-degree vertices are A, C, D, F: four of them, an even number.

Example 2

Day 1: a plan the handshake lemma rules out

Senna’s plan has 3 servers with exactly 5 cables each, and every other computer with exactly 2 cables. Show that no number of other computers makes this possible. Then find how many cables a plan with 4 such servers and 8 other computers needs, and show that plan can be built.

Solution

The servers have odd degree and every other computer even degree, so there are exactly 3 odd-degree vertices. Result 2 forbids an odd count, whatever the number of other computers. In sums: with m other computers the degree sum is 15 + 2m, odd, so it cannot equal 2\lvert E\rvert.

With 4 servers and 8 others the degree sum is 4 \cdot 5 + 8 \cdot 2 = 36, so any such network has \displaystyle \frac{36}{2} = 18 cables. The lemma gives the count but not existence, so build one. Cable the servers s_1, s_2, s_3, s_4 to each other: 6 cables, 3 at each server. Give server s_i two computers c_i and c_i', with cables s_i c_i, s_i c_i' and c_i c_i'. Each server now has 3 + 2 = 5 cables, each other computer has 2, and there are 6 + 4 \cdot 3 = 18 cables.

Example 3

Day 1: cabling every pair

Senna considers cabling every pair of 14 computers directly. How many cables, and how many plugs per computer? What is the largest number of computers that can be cabled pair by pair with at most 300 cables?

Solution

The network is K_{14}. Each computer is joined to the other 13, so it needs 13 plugs. By Result 3 there are \displaystyle \frac{14 \cdot 13}{2} = 91 cables, the same as \binom{14}{2}.

For the second part, K_n needs \displaystyle \frac{n(n-1)}{2} \le 300, that is n(n - 1) \le 600. The product n(n - 1) grows with n, and 25 \cdot 24 = 600 while 26 \cdot 25 = 650. So 25 computers is the most, using exactly 300 cables.

Example 4

Day 1: which sizes allow a 3-regular graph

For which n is there a 3-regular graph on n vertices?

Solution

First, what is forced. By Result 4, 3n = 2\lvert E\rvert is even, so n is even. A degree is at most n - 1, so 3 \le n - 1 and n \ge 4.

Now show every even n \ge 4 works. Number the vertices 0, 1, \ldots, n - 1 around a circle and join each vertex i to the two beside it, i + 1 and i - 1, and to the one opposite, \displaystyle i + \frac{n}{2}, all taken modulo n. The three are different: i + 1 \ne i - 1 since n > 2, and \displaystyle \frac{n}{2} equals neither 1 nor n - 1 when n \ge 4. The rule is symmetric (if j is beside or opposite i, then i is beside or opposite j), so each edge is counted from both ends and every degree is 3. Figure 3 shows n = 8, with \displaystyle \frac{3 \cdot 8}{2} = 12 edges; for n = 4 the rule gives K_4.

Figure 3A 3-regular graph on 8 vertices. The crossing at the center is not a vertex.

So a 3-regular graph on n vertices exists exactly when n is even and n \ge 4.

Example 5

Day 2: a list with an even sum that is not a degree sequence

Is (4, 4, 3, 2, 1) the degree sequence of a simple graph?

Solution

The quick tests pass: the sum 4 + 4 + 3 + 2 + 1 = 14 is even, and no entry exceeds n - 1 = 4. They are needed but not enough.

Figure 4Two vertices of degree 4 on five vertices are joined to everything, so every vertex has degree at least 2.

A direct reason. With 5 vertices, a vertex of degree 4 is adjacent to every other vertex. Call the two such vertices p and q. Every other vertex is adjacent to both, so it has degree at least 2 (Figure 4). A vertex of degree 1 is impossible. So the list is not graphic.

The removal test. Delete the first 4 and lower the next four entries: (4, 3, 2, 1) \to (3, 2, 1, 0). Delete the 3 and lower the next three: (2, 1, 0) \to (1, 0, -1). A degree cannot be negative, so by Result 8 neither list was graphic.

Example 6

Day 2: running the removal test and building the graph

Decide whether (5, 4, 4, 3, 3, 2, 2, 1) is graphic, and if it is, build a graph.

Solution

The sum is 24, even. Each row deletes the first entry, lowers that many of the next entries by 1, and re-sorts.

Deleted	List after lowering, sorted
	(5, 4, 4, 3, 3, 2, 2, 1)
5	(3, 3, 2, 2, 2, 1, 1)
3	(2, 2, 1, 1, 1, 1)
2	(1, 1, 1, 1, 0)
1	(1, 1, 0, 0)
1	(0, 0, 0)

The last list is graphic (three isolated vertices), so by Result 8 every list above it is, the first one included.

To build a graph, name the vertices a to h with the required degrees 5, 4, 4, 3, 3, 2, 2, 1, and let each row’s deleted vertex take its edges to the vertices whose entries it lowered. Vertex a is joined to b, c, d, e, f. Still needed: b 3, c 3, d 2, e 2, g 2, f 1, h 1. Vertex b is joined to c, d, e. Still needed: c 2, g 2, then d, e, f, h 1 each. Vertex c is joined to g and d; then g to e; then f to h. That is \displaystyle 5 + 3 + 2 + 1 + 1 = 12 = \frac{24}{2} edges, and Figure 5 shows the degrees come out right.

Figure 5A graph with degree sequence (5, 4, 4, 3, 3, 2, 2, 1), built by joining each deleted vertex of Example 6 to the vertices whose entries it lowered.

Example 7

Day 2: a dense list through its complement

Is (6, 6, 6, 5, 5, 5, 4, 3) graphic? How many edges would a graph with these degrees have?

Solution

The sum is 40, so such a graph has 20 edges. The degree bounds agree: with \delta = 3 and \Delta = 6, Result 5 asks 8 \cdot 3 = 24 \le 40 \le 48 = 8 \cdot 6.

The removal test would lower six entries at the first step. The complement is lighter: by Result 6, with n - 1 = 7, test 7 - d for each entry, giving (4, 3, 2, 2, 2, 1, 1, 1), sum 16.

\begin{aligned} (4, 3, 2, 2, 2, 1, 1, 1) &\to (2, 1, 1, 1, 1, 1, 1) \\ &\to (1, 1, 1, 1, 0, 0) \\ &\to (1, 1, 0, 0, 0) \to (0, 0, 0, 0). \end{aligned}

All zeros, so the complement list is graphic, and so is the original: take the complement of a graph with the complement list. That complement graph has 8 edges, and 20 + 8 = 28 = \binom{8}{2}, as Result 6 requires.

Boundaries

Simple graphs only. In a multigraph a loop adds 2 to its vertex’s degree and repeated edges count separately. The handshake lemma and Result 2 survive, but the bound \deg(v) \le n - 1 and the removal test do not (two vertices joined by three edges have degrees (3, 3)), and neither does Result 7: with ab doubled and one edge bc, the degrees are 2, 3, 1.
Finite graphs. Every result here sums or counts over a finite vertex set.
The sum test is one-way. An odd degree sum proves a list is not graphic. An even sum proves nothing, as (4, 4, 3, 2, 1) shows.
The handshake lemma counts but does not build. It gives the number of edges any graph with the given degrees must have, not that one exists.
A degree sequence does not fix the graph. Different graphs can share one; telling them apart is the subject of Graph isomorphism: when two drawings are the same graph.

Where this goes next

Degrees decide whether a network can be traced in one stroke, using every edge once: that needs the graph to be connected and every degree even (Euler paths and circuits), and connected graphs come from Walks, paths, cycles and connected graphs, the next lesson. The degree sum, now taken over the regions of a drawing, gives the edge bounds behind Planar graphs and Euler's formula. Degree sequences are the first test in Graph isomorphism: when two drawings are the same graph, and degrees are the row sums of the adjacency matrix.

Exercises

Day 1: degrees and the handshake lemma

Let V = \{p, q, r, s, t, u\} and E = \{pq, pr, qr, qs, rt, st, su\}. Find every degree, check the handshake lemma, and name the vertices of odd degree.
A graph has 9 vertices: six of degree 4 and three of degree 2. How many edges does it have?
A graph has 15 edges, every vertex has degree 3 or 4, and exactly six vertices have degree 3. How many vertices does it have?
Explain why no graph has degrees 5, 4, 3, 3, 2, 2, 2.

Day 1: complete and regular graphs

Find the degree of each vertex of K_{20} and its number of edges.
A complete graph has 153 edges. How many vertices does it have?
Senna has 30 computers. How many cables join every pair, and how many plugs does each computer need? How many if she splits them into five groups of 6 and cables every pair within each group only?
A 4-regular graph has 26 edges. How many vertices does it have?
For which n is there a 5-regular graph on n vertices? Give a construction.

Day 2: degree sequences

Show that (3, 3, 1, 1) is not graphic, once directly and once by the removal test.
Run the removal test on (3, 3, 3, 3, 2) and draw a graph with this degree sequence.
Is (5, 3, 3, 2, 1) graphic?
Show that (4, 4, 4, 1, 1, 1, 1) is not graphic by the removal test, and give a counting reason as well.
Run the removal test on (4, 4, 3, 3, 2, 2, 2, 2) and give the edges of a graph with this degree sequence.
Give a graph on 5 vertices in which exactly two vertices have the same degree and the other three degrees are all different.

Day 2: complements and bounds

A graph G has 11 vertices and 20 edges. How many edges does \overline{G} have? If \deg_G(v) = 7, what is \deg_{\overline{G}}(v)?
A graph has 12 vertices, \delta(G) = 3 and \Delta(G) = 7. Between which bounds must \lvert E \rvert lie? What are \delta and \Delta of the complement?
Use the complement to decide whether (7, 7, 7, 6, 6, 6, 6, 5, 4) is graphic. How many edges would such a graph have?
G is a 4-regular graph on 10 vertices. Show that \overline{G} is regular, and find the number of edges of G and of \overline{G}.

Reasoning

Prove that in every graph with an odd number of vertices, some vertex has even degree.
Prove that a graph with n vertices and more than n edges has a vertex of degree at least 3.
Refute with a counterexample: “a list of n nonnegative integers with an even sum and every entry at most n - 1 is graphic.” Do not use (4, 4, 3, 2, 1).
Let G have n vertices with \displaystyle \delta(G) \ge \frac{n - 1}{2}. Prove that any two non-adjacent vertices have a common neighbor.
Prove that an r-regular graph on n vertices exists exactly when 0 \le r \le n - 1 and rn is even.

Answers

\deg(p) = 2, \deg(q) = 3, \deg(r) = 3, \deg(s) = 3, \deg(t) = 2, \deg(u) = 1. The sum is 14 = 2 \cdot 7. Odd: q, r, s, u, four vertices.
15 edges: the degree sum is 6 \cdot 4 + 3 \cdot 2 = 30 = 2\lvert E \rvert.
9 vertices. With x vertices of degree 4, 6 \cdot 3 + 4x = 2 \cdot 15 = 30, so x = 3. One such graph exists: the removal test takes (4, 4, 4, 3, 3, 3, 3, 3, 3) to zeros.
The sum 5 + 4 + 3 + 3 + 2 + 2 + 2 = 21 is odd, but it must be 2\lvert E \rvert.
Degree 19; \displaystyle \frac{20 \cdot 19}{2} = 190 edges.
18: \displaystyle \frac{n(n-1)}{2} = 153 gives n(n - 1) = 306 = 18 \cdot 17.
All pairs: K_{30}, \displaystyle \frac{30 \cdot 29}{2} = 435 cables, 29 plugs each. Five groups: five copies of K_6, 5 \cdot 15 = 75 cables, 5 plugs each.
13: 4n = 2 \cdot 26 = 52.
Exactly the even n \ge 6. Necessary: 5n even forces n even, and 5 \le n - 1. For even n \ge 6, join i to i \pm 1, i \pm 2 and \displaystyle i + \frac{n}{2} modulo n; these five are different because \displaystyle \frac{n}{2} \ne 1, 2, n - 2, n - 1 when n \ge 6, and the rule is symmetric. Other constructions work too.
Directly: on 4 vertices, a vertex of degree 3 is adjacent to all others, so with two of them every vertex has degree at least 2. Removal test: (3, 3, 1, 1) \to (2, 0, 0) \to (-1, -1), negative.
The lists are (3, 3, 3, 3, 2), (2, 2, 2, 2), (1, 1, 2) sorted to (2, 1, 1), then (0, 0): graphic. Edges: ab, ac, ad, bc, bd, ec, ed, with e of degree 2. Other graphs work too.
No: 5 vertices allow degree at most 4.
The lists are (4, 4, 4, 1, 1, 1, 1), (3, 3, 1, 1, 0, 0), (2, 0, 0, 0, 0), then (-1, -1, 0, 0), negative. Counting: each degree-4 vertex has at most 2 neighbors among the other two such vertices, so at least 2 among the four degree-1 vertices: at least 6 edges reach those vertices, but they have only 4 edge ends between them.
The lists are (4, 4, 3, 3, 2, 2, 2, 2), (3, 2, 2, 2, 2, 2, 1), (2, 2, 1, 1, 1, 1), (1, 1, 1, 1, 0), (1, 1, 0, 0), (0, 0, 0): graphic. One graph: ab, ac, ad, ae, bc, bd, bf, gh, gc, hd, fe. Other graphs work too.
One answer: edges ab, ac, ad, bc, with e isolated. Degrees 3, 2, 2, 1, 0: only b and c share. Other graphs work too. (Result 7 says some pair must share.)
\binom{11}{2} - 20 = 55 - 20 = 35 edges; \deg_{\overline{G}}(v) = 10 - 7 = 3.
12 \cdot 3 \le 2\lvert E\rvert \le 12 \cdot 7, so 18 \le \lvert E \rvert \le 42. The complement has degrees 11 - \deg_G, so \delta = 11 - 7 = 4 and \Delta = 11 - 3 = 8.
Graphic. The complement list 8 - d is (4, 3, 2, 2, 2, 2, 1, 1, 1). The test gives (2, 2, 1, 1, 1, 1, 1, 1) after sorting, then (1, 0, 1, 1, 1, 1, 1): six 1s and a 0, which pair off into three edges. The original sum is 54, so 27 edges.
Each degree in \overline{G} is 9 - 4 = 5, so \overline{G} is 5-regular. G has \displaystyle \frac{4 \cdot 10}{2} = 20 edges and \overline{G} has \displaystyle \frac{5 \cdot 10}{2} = 25; together 45 = \binom{10}{2}.
If every vertex had odd degree, the number of odd-degree vertices would be the number of vertices, odd, against Result 2. \square
By Result 5, n\,\Delta(G) \ge 2\lvert E \rvert > 2n, so \Delta(G) > 2; degrees are integers, so some vertex has degree at least 3. \square
(5, 5, 5, 1, 1, 1): sum 18, entries at most 5 = n - 1. Each degree-5 vertex is adjacent to all others, so every vertex has degree at least 3, and degree 1 is impossible.
Let u, v be non-adjacent. Their neighbors lie among the other n - 2 vertices. Since \deg(u) + \deg(v) \ge n - 1 > n - 2, the two neighbor sets cannot be disjoint, by pigeonhole, so they share a vertex. \square
Necessary: degrees are at most n - 1, and rn = 2\lvert E\rvert. Sufficient: number the vertices 0, \ldots, n - 1 modulo n. If r is even, join i to \displaystyle i \pm 1, \ldots, i \pm \frac{r}{2}; since \displaystyle \frac{r}{2} < \frac{n}{2} these r vertices are different, and the rule is symmetric, so every degree is r. If r is odd, n is even; join i to \displaystyle i \pm 1, \ldots, i \pm \frac{r - 1}{2} and to \displaystyle i + \frac{n}{2}, again r different vertices since \displaystyle \frac{r - 1}{2} < \frac{n}{2}. \square