Lecture 33 — Pigeonhole Principle, Introduction to Graph Theory

lecture
discrete-math
counting
graph-theory

Two topics: the pigeonhole principle, used to prove that a selection of numbers must contain a pair (or a triple, or two subsets) of a certain kind, and the first definitions of graph theory: graphs, loops, multiple edges, simple graphs, degree, the Handshake Theorem and degree sequences. Pre-work: Video 042 (The Pigeonhole Principle) and Video 043 (Introduction to Graph Theory). The principle, its generalised form, how to choose the pigeons and the holes, and more examples are in pigeonhole-principle. Graphs, degree, the Handshake Theorem and its corollary, and degree sequences are in [graphs].

Goals

  1. Learn how to use the pigeonhole principle to solve various problems.
  2. Understand the basic terminology and definitions of graph theory.

Two questions to keep in mind:

The pigeonhole principle

If \(n\) pigeons fly into \(m\) pigeonholes and \(n > m\), then at least one pigeonhole contains two or more pigeons.

Ten pigeons and nine holes: if every hole held at most one pigeon, the holes would hold at most nine pigeons, and there are ten. So some hole holds two. That is the whole proof, for any \(n > m\).

In a proof the pigeons are the objects chosen and the holes are categories that every object falls into. The skill is choosing the holes so that two pigeons in one hole is exactly the thing to be proved. In each problem below the holes are a partition of the set the numbers come from, built so that two chosen numbers in the same part give the pair that is wanted.

Many of these problems ask for the largest selection with some property. The answer then needs two halves:

  1. A selection of that size exists. Write one down.
  2. No larger selection exists. This is the pigeonhole half.

Worked: no two consecutive

What is the largest number of integers that can be selected from \(\{1, 2, \dots, 100\}\) such that no two selected integers are consecutive?
A. 49
B. 50
C. 51
D. 52
E. 99

Answer: B, 50.

50 is possible. Take the odd numbers \(1, 3, 5, \dots, 99\). There are 50 of them, and any two differ by at least 2, so no two are consecutive.

More than 50 is impossible. Split \(\{1, 2, \dots, 100\}\) into the 50 pairs

\[\{1, 2\},\ \{3, 4\},\ \{5, 6\},\ \dots,\ \{99, 100\}.\]

Every number is in exactly one pair, and each pair is two consecutive numbers. Choose more than 50 numbers. They are the pigeons, the 50 pairs are the holes, and by the pigeonhole principle some pair has both of its numbers chosen. Those two are consecutive.

Figure 1: The numbers 1 to 100 split into 50 pairs of consecutive numbers, the holes. A selection with no two consecutive numbers takes at most one number from each pair, so it has at most 50 numbers. The odd numbers, shaded, take exactly one from each pair and reach 50. A 51st number would have to go into a pair that already has one, and would sit next to it.

The other options:

  • A, 49, can be done (drop one odd number), but it is not the largest.
  • C, 51, and D, 52, are both more than 50, so the pigeonhole argument rules them out.
  • E, 99, leaves out only one number. Whichever number \(k\) is left out, at least one of \(\{1, \dots, k-1\}\) and \(\{k+1, \dots, 100\}\) has two or more numbers in it, and each of those is a run of consecutive numbers.

Worked: two numbers that sum to 101

Prove that if 51 numbers are chosen from \(\{1, 2, \dots, 100\}\), then two of the chosen numbers sum to 101.

Pair each number with the number it adds to 101 with:

\[P_1 = \{1, 100\},\ P_2 = \{2, 99\},\ P_3 = \{3, 98\},\ \dots,\ P_{50} = \{50, 51\}.\]

In general \(P_i = \{i, 101 - i\}\) for \(1 \le i \le 50\). These 50 sets are disjoint and between them contain every number from 1 to 100 exactly once, since \(i\) runs over \(1, \dots, 50\) and \(101 - i\) runs over \(100, \dots, 51\).

Proof. Choose 51 numbers from \(\{1, 2, \dots, 100\}\). Each lies in exactly one of the 50 sets \(P_1, \dots, P_{50}\). Since \(51 > 50\), by the pigeonhole principle there is some \(i\) with \(1 \le i \le 50\) such that both numbers in \(P_i\) were chosen. Those two numbers are \(i\) and \(101 - i\), and \(i + (101 - i) = 101\). \(\square\)

51 is the smallest number that works. The 50 numbers \(1, 2, \dots, 50\) contain no such pair, since the largest sum of two of them is \(49 + 50 = 99\).

Figure 2: The holes for the sum-101 problem. Each arc joins two numbers that add to 101, \(i\) and \(101 - i\), and the arcs nest because as one end moves in by one the other moves in by one too. There are 50 arcs and every number from 1 to 100 is the end of exactly one. 51 chosen numbers are more than the 50 arcs, so some arc has both of its ends chosen, and those two numbers sum to 101.

Worked: no three consecutive

What is the maximum number of integers that can be chosen from \(\{1, 2, \dots, 60\}\) such that no three of the chosen numbers are consecutive?

“No three consecutive” means there is no integer \(a\) with \(a\), \(a + 1\) and \(a + 2\) all chosen.

Answer: 40.

40 is possible. Choose every number that is not a multiple of 3, that is, every number congruent to 1 or 2 mod 3:

\[1, 2,\ 4, 5,\ 7, 8,\ \dots,\ 58, 59.\]

Any three consecutive integers include a multiple of 3, which was not chosen, so no three chosen numbers are consecutive. Two of every three numbers are chosen, \(60 \cdot \frac23 = 40\) in all.

41 or more is impossible. Split \(\{1, 2, \dots, 60\}\) into the 20 blocks

\[\{1, 2, 3\},\ \{4, 5, 6\},\ \{7, 8, 9\},\ \dots,\ \{58, 59, 60\}.\]

A block with all three of its numbers chosen gives three consecutive chosen numbers, so a good selection takes at most 2 from each block, at most \(2 \cdot 20 = 40\) in all. If 41 or more numbers are chosen then, since \(41 > 40 = 2 \cdot 20\), some block has all 3 of its numbers chosen.

This last step is the pigeonhole principle with “more than one” replaced by “more than two”: if more than \(2m\) pigeons go into \(m\) holes, some hole gets at least 3. If every hole had at most 2 there would be at most \(2m\) pigeons. It is the generalised form in pigeonhole-principle.

Figure 3: The numbers 1 to 60 split into 20 blocks of three consecutive numbers. A block with all three chosen breaks the rule, so a good selection takes at most 2 from each block, at most 40 in all, and 41 numbers force some block to be full. Taking the first two of every block, shaded, and leaving out the multiples of 3, struck through, reaches 40. Two blocks side by side never make a run of three, because the multiple of 3 between them is missing.

Worked: two subsets with the same sum

Show that if \(A\) is any 6-element subset of \(\{1, 2, \dots, 12\}\), then \(A\) has distinct subsets \(X\) and \(Y\) such that the sum of the elements in \(X\) equals the sum of the elements in \(Y\).

For example, \(A = \{2, 4, 6, 8, 10, 12\}\) has \(X = \{6\}\) and \(Y = \{2, 4\}\), both summing to 6. The task is to show such a pair exists for every \(A\), without knowing what \(A\) is.

The pigeons are the subsets of \(A\), the holes are the possible sums.

Pigeons. Write \(A = \{a_1, a_2, \dots, a_6\}\) with \(1 \le a_1 < a_2 < \cdots < a_6 \le 12\), all integers. \(A\) has

\[|\mathcal{P}(A)| = 2^{|A|} = 2^6 = 64\]

subsets, counting \(\emptyset\) and \(A\) itself (sets-and-set-notation).

Holes. For a subset \(S \subseteq A\) let \(\Sigma(S)\) be the sum of its elements, with \(\Sigma(\emptyset) = 0\). Every element is positive, so a subset’s sum is at least 0 and at most the sum of all of \(A\):

\[0 \le \Sigma(S) \le a_1 + a_2 + \cdots + a_6.\]

The six elements of \(A\) are six different integers that are at most 12, so the largest they can be is \(7, 8, 9, 10, 11, 12\):

\[a_1 + a_2 + \cdots + a_6 \le 7 + 8 + 9 + 10 + 11 + 12 = 57.\]

So every subset sum is one of the 58 integers \(0, 1, 2, \dots, 57\).

Conclusion. 64 subsets, each with a sum among 58 possible values. Since \(64 > 58\), by the pigeonhole principle two different subsets \(X \neq Y\) of \(A\) have the same sum. \(\square\)

The bound on the sum is the step that needs care. Bounding it by the sum of the whole of \(\{1, \dots, 12\}\), which is 78, gives 79 holes for 64 pigeons, and the argument says nothing.

Figure 4: The subset-sum argument for \(A = {2, 4, 6, 8, 10, 12}\). Each of the 64 subsets of \(A\), on the left, goes to its sum, on the right. However \(A\) is chosen, its sum is at most \(7 + 8 + \cdots + 12 = 57\), so the sums lie among the 58 values 0 to 57. Sending 64 subsets to 58 values must send two subsets to the same value. Here \({6}\) and \({2, 4}\) both go to 6.

Disjoint subsets. If \(X\) and \(Y\) share elements, take the shared ones out of both. The sums both drop by the same amount, so they stay equal, and \(X - Y\) and \(Y - X\) are disjoint. Neither is empty: if \(X - Y\) were empty then \(X\) would be a proper subset of \(Y\), and \(Y\) would have the larger sum, since every element is positive.

Graphs

A graph \(G\) is a non-empty set of vertices \(V(G)\) and a (possibly empty) set of edges \(E(G)\), where each edge is associated with a set consisting of either one or two vertices.

The vertices an edge is associated with are its endpoints. A graph is drawn with a dot for each vertex and, for each edge, a line joining its two endpoints, or, for an edge with a single endpoint, a line from that dot back to itself. A graph can have no edges at all, just dots, but it must have at least one vertex.

  • A loop is an edge with only one endpoint.
  • Multiple edges (also called parallel edges) are two or more edges with the same endpoints.
  • A graph is simple if it has no loops and no multiple edges.

The degree of a vertex \(v\), written \(\deg(v)\), is the number of edge ends incident with it. An ordinary edge has one end at each of its endpoints. A loop has both of its ends at the same vertex, so a loop adds 2 to the degree.

Figure 5: Degrees counted as edge ends. Left: a graph with a pair of multiple edges between the two top-left vertices and a loop at the bottom-right vertex. The bottom-right vertex has degree 4: one end each from the edges to its two neighbours, and two from the loop. The top-middle vertex has degree 5, two of them from the multiple edges. The degrees add to 18, and there are 9 edges. Right: a simple graph, one vertex joined to four others. The centre has degree 4 and each of the others degree 1, a total of 8 for 4 edges.

The Handshake Theorem

The Handshake Theorem. The sum of the degrees of a graph is twice the number of edges. If \(G\) is a graph with \(V(G) = \{v_1, v_2, \dots, v_n\}\) and \(|E(G)| = e\), then \[\sum_{i=1}^{n} \deg(v_i) = 2e.\]

Why. Adding up the degrees counts every edge end in the graph once, at the vertex it touches. Every edge has exactly two ends, an ordinary edge one at each endpoint and a loop both at its one endpoint. So the total number of ends is \(2e\). In the left graph above, 9 edges give 18 ends, and the degrees add to 18.

So the sum of the degrees is always even. That gives the corollary:

Corollary. Every graph has an even number of vertices of odd degree.

Proof. Split the vertices into those of even degree and those of odd degree:

\[2e = \sum_{\deg(v) \text{ even}} \deg(v) \;+\; \sum_{\deg(v) \text{ odd}} \deg(v).\]

The first sum adds even numbers, so it is even. The left side is even. So the second sum, the difference of two even numbers, is even too. It is a sum of odd numbers, and a sum of odd numbers is even only when there is an even number of them. So the number of vertices of odd degree is even. \(\square\)

In the left graph above the odd-degree vertices are the ones of degree 5 and 1, two of them. In the right graph they are the four vertices of degree 1.

The proof of the theorem, and more on degree, are in graphs.

Worked: which statement about degrees is true

Which of the following is true?
(a) In any graph there is an even number of vertices of even degree.
(b) In any graph there is an odd number of vertices of even degree.
(c) In any graph there is an even number of vertices of odd degree.
(d) In any graph there is an odd number of vertices of odd degree.

Answer: (c). It is the corollary of the Handshake Theorem just proved:

\[\sum_{i=1}^{n} \deg(v_i) = \deg(v_1) + \deg(v_2) + \cdots + \deg(v_n) = 2e\]

is even, so the odd degrees among \(\deg(v_1), \dots, \deg(v_n)\) must come in an even number.

Each of the others says “in any graph”, so one graph where it fails is enough to show it is false.

  • (a) is false. One vertex joined to four others has degrees \(4, 1, 1, 1, 1\): one vertex of even degree. (A graph with a single vertex and no edges, one vertex of degree 0, also works.)
  • (b) is false. Four vertices in a path have degrees \(1, 2, 2, 1\): two vertices of even degree.
  • (d) is false. Two vertices joined by one edge have degrees \(1, 1\): two vertices of odd degree. In fact (d) is false for every graph, by (c).

Statements (a) and (b) fail because the number of even-degree vertices can be anything: the corollary controls only the odd ones.

Figure 6: Three graphs that each break one of the false statements. Even degrees are blue and odd degrees red. Left: one vertex joined to four others has just one vertex of even degree, so the number of even-degree vertices need not be even. Middle: a path of four vertices has two vertices of even degree, so it need not be odd either. Right: a single edge has two vertices of odd degree, so the number of odd-degree vertices is not odd. In every graph, as in these three, the red labels come in an even number.

Worked: degree sequences

The list of the degrees of the vertices of a graph is its degree sequence.

For each of the following lists, draw a simple graph with vertices whose degrees are the numbers in the list, or explain why no such graph exists.
(a) 2, 2, 2, 2
(b) 3, 2, 1
(c) 4, 3, 2, 2, 2, 2, 1, 1
(d) 1, 1, 1, 1
(e) 5, 5, 5, 5, 5, 5

Two checks rule a list out straight away:

  • The sum must be even, by the Handshake Theorem. Equivalently, the list must contain an even number of odd entries.
  • In a simple graph with \(n\) vertices every degree is at most \(n - 1\). With no loops and no multiple edges, a vertex has at most one edge to each of the other \(n - 1\) vertices.

Passing both checks does not guarantee a graph, so for a list that passes, draw one.

List Sum Largest entry vs \(n - 1\) Simple graph?
(a) 2, 2, 2, 2 8 \(2 \le 3\) yes: a square, 4 edges
(b) 3, 2, 1 6 \(3 > 2\) no
(c) 4, 3, 2, 2, 2, 2, 1, 1 17, odd \(4 \le 7\) no
(d) 1, 1, 1, 1 4 \(1 \le 3\) yes: two separate edges
(e) 5, 5, 5, 5, 5, 5 30 \(5 \le 5\) yes: every pair of the 6 vertices joined, 15 edges
  • (a) Four vertices around a square, each joined to its two neighbours. Each has degree 2, and \(8 = 2 \cdot 4\) edges.
  • (b) There are only three vertices, so in a simple graph a vertex can be joined to at most the other two, and degree 3 is impossible. The sum, 6, is even, so the Handshake Theorem alone does not rule it out. Without the word simple there is a graph: join the degree-3 vertex to the degree-2 vertex by two multiple edges and to the degree-1 vertex by one edge. That graph has multiple edges, so it is not simple.
  • (c) The odd entries are 3, 1 and 1, three of them. A graph must have an even number of vertices of odd degree, so no graph exists, simple or not. Equivalently, the sum is 17, which is not \(2e\) for any \(e\).
  • (d) Two edges with no vertex in common. Each vertex is the end of one edge.
  • (e) Six vertices, every pair joined by an edge. Each vertex is joined to the other 5. There are \(\binom62 = 15\) edges, and \(6 \cdot 5 = 30 = 2 \cdot 15\).

Figure 7: Simple graphs for the three lists that can be realised, each vertex labelled with its degree. (a) 2, 2, 2, 2: a square, each vertex joined to its two neighbours. (d) 1, 1, 1, 1: two edges sharing no vertex. (e) 5, 5, 5, 5, 5, 5: six vertices with every pair joined, 15 edges, so each vertex is joined to all 5 others.

Figure 8: Why lists (b) and (c) have no simple graph. (b) 3, 2, 1: each vertex is labelled with the degree it needs. With three vertices, the vertex that needs degree 3 can be joined to only the 2 others, since a simple graph allows at most one edge to each. A third edge would need a fourth vertex, or a second edge to a vertex it already meets. Allowing multiple edges gives a graph, in the middle, but it is not simple. (c) 4, 3, 2, 2, 2, 2, 1, 1: three entries are odd, and the number of odd-degree vertices in any graph is even.

More on degree sequences, including a list that passes both checks and still has no simple graph, is in graphs.

See also