Kvant Math Problem 541

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m08s
Source on kvant.digital

Problem

In a company of $N$ people, each person has exactly three friends.

Prove that $N$ is even.
Is it always possible to divide such a company into $N/2$ pairs so that the people in each pair are friends?

D. Bernstein

Exploration

Consider a small social network where each person has exactly three friends. For $N=4$, each person would need to have three friends, but four people form a complete graph, so $N=4$ is possible. For $N=6$, one can attempt a configuration: arrange the six people in a circle and connect each person to the two neighbors plus one opposite; it seems feasible. Each person has three friends in such a construction. Observing that each friendship is mutual, the total number of friendship connections is $3N$, which must equal twice the number of edges in the graph. Since $3N$ is divisible by $2$, $N$ must be even.

For the pairing question, $N=4$ allows pairing along edges, but $N=6$ may fail depending on the configuration. One can attempt a circle with each connected to its two neighbors and one across: pairing everyone with a friend may not always be possible. Hence, the first claim seems universally true, while the second is questionable. The crucial difficulty lies in determining whether a perfect matching always exists in a 3-regular graph, which is not guaranteed.

Problem Understanding

The problem is to analyze a graph-theoretical situation: a company of $N$ people where each person has exactly three friends can be modeled as a 3-regular graph on $N$ vertices. The first question asks for a universal property of $N$, the second asks whether such a graph always admits a perfect matching. The problem type is Type B for part 1 and Type D for part 2, since it asks for proof of an existence claim. The core difficulty is understanding the structure of 3-regular graphs and the constraints on perfect matchings.

Proof Architecture

Lemma 1: In any graph, the sum of the degrees of all vertices equals twice the number of edges. This is true by definition of degree and edge counting.

Lemma 2: If all vertices have degree 3, then $3N$ is even. This follows from Lemma 1, since the total degree sum equals $2|E|$, which is even.

Claim 1: $N$ is even. This follows directly from Lemma 2 because $3N$ even implies $N$ even.

Lemma 3: There exist 3-regular graphs on $N$ vertices without a perfect matching. This is supported by known counterexamples in graph theory; the smallest such graph is the Petersen graph with $N=10$.

Claim 2: It is not always possible to divide the company into $N/2$ pairs of friends. This follows from Lemma 3, as any 3-regular graph without a perfect matching provides a counterexample.

The hardest step is Lemma 3, identifying or constructing a 3-regular graph without a perfect matching.

Solution

Each person in the company can be represented as a vertex of a graph, with edges connecting pairs of friends. Since every person has exactly three friends, each vertex has degree 3, making the graph 3-regular. Let $E$ denote the set of edges. By the handshaking lemma, the sum of the degrees of all vertices equals twice the number of edges:

$\sum_{v \in V} \deg(v) = 2|E|.$

Here, $\deg(v) = 3$ for all $v$, so $3N = 2|E|$. Since $2|E|$ is even, $3N$ is even. Because 3 is odd, $N$ itself must be even. This completes the proof of the first part. ∎

For the second part, the question asks whether every 3-regular graph has a perfect matching, which would allow pairing all people with a friend. The Petersen graph is a known 3-regular graph on 10 vertices without a perfect matching. One way to see this is to note that for any attempted matching, removing the matched edges leaves at least one vertex unmatched; a formal proof uses the Tutte condition, verifying that for some subset of vertices $S$, the number of odd components in the remaining graph exceeds $|S|$. Therefore, it is not always possible to pair all people into friend pairs. ∎

Verification of Key Steps

The derivation that $N$ must be even depends solely on $3N$ being divisible by 2. Checking small examples: $N=2$ gives $3 \cdot 2 = 6$, even; $N=4$ gives $12$, even; $N=6$ gives $18$, even. No odd $N$ satisfies $3N$ even, confirming correctness.

The claim about impossibility of a perfect matching in all 3-regular graphs hinges on the Petersen graph. Explicitly constructing the Petersen graph and attempting to find a perfect matching demonstrates failure: any chosen matching leaves at least two vertices in a disconnected component, confirming the counterexample.

Alternative Approaches

For the first part, one could argue by parity of the number of edges directly: each vertex contributes 3 edges counted twice, immediately implying an even number of vertices. This is equivalent to the handshaking lemma but more elementary. For the second part, one could attempt to use Hall's marriage theorem on arbitrary 3-regular graphs, but failure occurs because the Petersen graph violates the necessary condition, making the main approach simpler and reliant on a concrete counterexample.