Double counting is a simple yet so powerful way to prove non-trivial theorems. Here, we present some applications of the double counting principle. Our main source is the excellent book “Extremal Combinatorics” by Stasys Jukna [1]. A newer edition from the one in the picture (which shows the book I have) is also available now.

Basic idea: Let be a 0/1 matrix. Then the number of 1s (and of course of 0s) can be counted in two ways: A) Count for each row the number of 1s and sum over all rows. (B) Count for each column the number of 1s and sum over all columns.

Let’s start first with a basic double counting argument, known as the handshaking lemma.

**Handshaking lemma**: At a party the number of guests who shake hands an odd number of times is even.

**Proof**: Let be the number of guests and the number of pairs of guests who gave their hands respectively. Now let’s define a matrix which is and its (i,j)-th entry is 1 if guest i is one of the two people in the j-th pair, otherwise it is 0. Now double count the number of ones. For convenience let’s call the number of times guest shook his hand with someone else in the party. Clearly double counting the number of 1s gives . The 2 in the righthandside is because the number of ones per column is 2. Now let’s break the lefthandside . We observe that the righthandside is definitely an even number and the lefthandside is a sum of odd numbers. In order to be even the number of summands has to be even! This means in terms of the party, the number of guests who shake hands an odd number of times is even. **QED**

Well that was easy. But never forget one of the teachings of the Aesop’s fables (never underestimate the power of something “small”). Let me solve a riddle which I had given you some weeks ago.

**Riddle of December 2nd**: You can always find in a simple undirected graph of minimum degree two spanning edge disjoint subgraphs of minimum degree at least . Give also an algorithmic procedure to find such subgraphs.

**Proof Sketch**: Well, we know from the handshaking lemma that the number of vertices with odd degree is even. Let’s add a matching to make each vertex have an even degree. The resulting graph is Eulerian. Color the edges incident to any vertex in a fair way. This gives you the result. Argue why. **QED**

Let’s now move to some a generalization of the handshaking lemma. Specifically, the lemma in terms of graphs tells us that the sum of degrees is equal to 2 times the number of edges. What about hypergraphs . Hypergraphs again have a set of vertices but edges may consist of more than two vertices. By double counting we obtain the following lemma.

**Hypergraph handshaking lemma**: Let be the edge set of a hypergraph on the vertex set . Then, .

**Exercise 1 (eq. 1.8, Jukna, p.16):** Let’s play further. Fix a subset . Let’s prove .

**Proof:**

**QED**.

**Exercise 2 (eq. 1.9, Jukna, p.16):** Let’s play even further. Let’s prove .

**Proof:**

I guess you have got the point: indicator variables, exchange summation order. Let’s do the last part of this exercise.

**QED**

Now let’s move to a graph theory exercise which nicely illustrates the double counting idea.

**Problem:** Let be a bipartite graph with the following property: for any edge where , . Then .

**Proof:**

**QED**

Now, I will move to more interesting exercises. Let’s start by Turán’s number which is defined as the smallest number of -element subsets such that any -element subset of [n] contains at least one of these sets.

**Exercise 3 (See Proposition 1.8, Jukna p.16):** .

**Proof 1:** We will double count the number of 1s of an appropriately defined matrix . Let be the smallest -uniform family that has the Turán property. Let be a matrix where its (i,j)-th entry is 1 if the i-th member of is contained in the j-th k-element subset of [n]. Clearly from a fixed element subset we can create k-element subsets. This suggests that there are 1s per row. Furthermore, by the Turán property each column has at least one 1. Therefore which gives our theorem. **QED**

**Proof 2:** Turn proof 1 in a probabilistic proof using a first moment argument.

**Exercise 4 (See Exercise 1.22, Jukna p.22):** Let be a family of -element subsets of [n] such that every -element subset is contained in at least one member of . What can you say about the size of using the previous exercise as your guide?

**Proof:** We define as a matrix where the (i,j)-th entry is an indicator variable of whether the -th member of contains the -th -element subset. Clearly again by double counting the number of 1s we obtain the following lower bound . Hence, $latex |\mathcal{F}|\geq\frac{{n \choose l}}{{k \choose l}}$.

Now, let’s have a look at the shadow of a family of sets. It is an important concept that appears a lot in extremal combinatorics.

**Exercise 5 (See Exercise 1.23, Jukna p.22):** Let be a family of -element subsets of [n]. Its shadow is the family of all those -element subsets which lie entirely in at least one member of . Show that the shadow satisfies .

Proof: Let’s create a matrix with rows and columns. We will place a 1 in its (i,j)-th entry if the -th element of the shadow is a subset of the -th element of , otherwise we will place a 0. Now let’s double count the 1s. Clearly each column contains ones. Furthermore, each row contains at most 1s, i.e., it can be generated from -element subsets. Therefore, . **QED**

Finally, I will conclude with a neat lemma, known as the Corrádi lemma. From Google scholar I get the feeling it was posted in a math competition in Hungary, see [2]. Before going into the statement and the proof of the lemma, three things. (1) Hungary has a lot of talent in discrete math. (2) The beauty of the lemma and all the above exercises is that -in my opinion- they can be solved from a smart high school student. (3) Try to solve it on your own to verify you have mastered double counting :-). In case you have no experience in extremal combinatorics, it will be on of your first steps teaching you also a useful technique.

**Corrádi’s Lemma (See Lemma 2.1, Jukna p.23):** Let be -element sets and be their union. If for all then .

This is the problem of the day for you.

[1] Extremal combinatorics, Stasys Jukna.

[2] Problem at Schweitzer competition, Corrádi

[…] Before we see it though let us see the rationale behind it. We may rewrite . This suggests that a double counting argument of permutations may turn out to be of use to us. […]