Graph Theory: From the Handshaking Lemma to the Marriage Theorem

Katsuhiro Ota (Professor, Department of Mathematics)

"At a party, the sum of the number of handshakes made by each attendee is always an even number."

This is a theorem that appears at the beginning of graph theory, called the "handshaking lemma." A graph, as shown in Figure 1, is a structure consisting of several vertices and the edges that connect them. In the problem of considering the number of handshakes at the party mentioned earlier, a graph can be created by representing the party attendees as vertices and connecting two people who shook hands with an edge. By the way, the proof of the handshaking lemma is as follows.

Since one handshake involves two attendees, the sum of the number of handshakes made by the attendees is twice the total number of handshakes. Therefore, it is an even number.

Although it can be proven without using the language of graphs, I think looking at the graph provides a clearer perspective.

By representing a problem with a graph, as in this example, we can highlight its essential parts, and by showing it in a diagram, we can appeal to the visual sense and make it more intuitive and easier to understand. Some things, like the internet, railway networks, and road networks, already look like graphs themselves. However, as in the example above, there are also graphs that represent relationships between people, and it can be said that graphs are potentially everywhere. Graph theory is the study of the various properties of such graphs. Below, I will introduce a part of the theory related to graph matching.

This time, the party is a matchmaking party (or perhaps it's better to call it a singles mixer). Suppose there are *n* men and *n* women in attendance. When the party is in full swing, we ask each attendee to name the people of the opposite sex they would be willing to marry (multiple answers are allowed), and then we consider creating as many married pairs as possible from the pairs who feel mutually that way. In this problem as well, if we connect pairs who are mutually willing to marry with an edge, a graph like the one in Figure 2 is created.

In Figure 3, I have tried creating some pairs. This way of selecting edges is called a matching. One man and one woman are left over without being paired, but is there a combination where everyone can get married? Actually, the answer is no. The reason is immediately obvious if you look at Figure 4. The four vertices with double circles are connected to only three other vertices in total, so one of the four people will inevitably be left over.

Like the vertices with double circles above—that is, if a group of people is competing for a smaller number of partners, someone will be unable to get married. However, it is known that if no such "group" exists anywhere, then everyone can be married. This is called the marriage theorem.

The problem of matching is often compared to marriage in the sense of creating one-to-one pairs, but it also applies to assignment problems, such as allocating jobs. Puzzles like Sudoku can also be seen as matching problems if we focus on the part of assigning which number to which square. By abstracting a problem into a structure called a graph, it becomes a concept applicable to various fields.