A nice story problem from Germany

(Choo Ray here.) I thought it may be a good idea to write about some of the more interesting problems that I have used in my recent sessions for students in the Singapore National Team. Let us begin with the following.

Germany National Olympiad 2020 Problem 2 In ancient times there was a Celtic tribe consisting of several families. Many of these families were at odds with each other, so that their chiefs would not shake hands.

At some point at the annual meeting of the chiefs they found it even impossible to assemble four or more of them in a circle with each of them being willing to shake his neighbour's hand.
To emphasize the gravity of the situation, the Druid collected three pieces of gold from each family. The Druid then let all those chiefs shake hands who were willing to. For each handshake of two chiefs he paid each of them a piece of gold as a reward.

Show that the number of pieces of gold collected by the Druid exceeds the number of pieces paid out by at least three.

Gold!

When preparing for sessions, I try to find problems from recent competitions around the world. My hope is that these questions are reflective of the current trends and I will get a sense of which ideas and topics tend to appear more often. However, it also means that I will encounter problems that are not to my strength and occasionally I struggle to even understand the solution! This particular problem from Germany was a rare instance where I managed to solve the problem on my own. I was helped by having encountered a similar idea a few months prior and I was quite pleased that I managed to adapt it to this problem.

Solutions

First of all, we need to reframe the question. Notice that the question centers around existence of handshakes between pairs of chiefs, which suggests a graph theoretic interpretation with chiefs as vertices and handshakes as edges. Then the condition "impossible to assemble four or more of them in a circle with each of them being willing to shake his neighbour’s hand" simply describes the absence of any cycles with length 4 or above. The number of pieces of gold collected by the Druid, "three from each family", is three times the number of vertices. On the other hand, for each handshake the Druid pays 2 gold, so the total number of gold paid is twice the number of edges.

Reframed Question In a graph with no cycles of length $\ge 4$, show that $3|V|-2|E|\ge 3$, or equivalently, $$|E|\le\frac{3(|V|-1)}{2}$$

Cycles of length four or more are disallowed.

Now here is my solution.

Solution 1: Maximal Path (inspired by Bulgaria National Olympiad 2023 Problem 1)

Consider the maximal path in the graph $v_1v_2v_3...v_{n-1}v_n$ (which must exist since the graph is finite). By virtue of it being maximal, $v_n$ cannot connect to any other vertices outside of this path, or else we would form a longer path. Furthermore, $v_n$ cannot connect to any of $v_1,v_2,...v_{n-3}$ since this would from a cycle of length $\ge 4$ which is not allowed.

Therefore, $v_n$'s neighbours must be $v_{n-1}$ and possibly $v_{n-2}$ only. ($*$)

If $v_n$ connects to just $v_{n-1}$, then we may remove it and induct on $|V|$. $|V|=1,2,3$ are obvious. Since removing $v_n$ removes only $1$ edge, adding it back we have by induction $$|E|\le\frac{3((|V|-1)-1)}{2}+1=\frac{3(|V|-1)}{2}-\frac{1}{2}$$

On the other hand, if $v_n$ connects to both $v_{n-1}$ and $v_{n-2}$, observe that the path $v_1v_2v_3...v_{n-2}v_{n}v_{n-1}$ is also maximal. Thus, by the argument $*$ above we know that $v_{n-1}$ has no other neighbours. Then removing both $v_{n-1}$ and $v_{n-2}$ removes just $3$ edges, again by induction $$|E|\le\frac{3((|V|-1)-2)}{2}+3=\frac{3(|V|-1)}{2}$$ So we are done.

With a maximal path (in black), the vertex at the end cannot have any red edges, so its neighbours are determined up to the existence of the green edge. When the green edge exists, we may make use of the new maximal path formed with the green edge.

I went to check the AoPS post and to my surprise, my solution was not on there! Instead, I was greeted with another idea, very interesting in its own right:

Solution 2: Spanning Trees (as outlined by Taha1381)

Consider a spanning tree on each connected component of the graph (a maximal spanning forest).

Each additional edge must form a cycle, since it must connect a pair of vertices from the same component, which already have a path between them using the component's spanning tree. By the question condition, this cycle can only be of length $3$. Let us call the other two edges in the cycle the associates of this new edge.

Consider two new edges $e_1,e_2$ and their associates. Let $e_1$ have associates $v_1v_2,v_1v_3$. Then $e_1=v_2v_3$. If $e_2$ has the same pair of associates $e_2=v_2v_3$ as well which is absurd. If $e_2$ shares just $1$ associate, WLOG $v_1v_2$, then $e_2$ and its other associate is some combination of $v_1v_4,v_2v_4$. However this forms a cycle of length 4 $v_1v_4v_2v_3$, contradiction.

Thus, by elimination, the only possibility is that any two edges have disjoint pairs of associates. Since our spanning forest has $\le|V|-1$ edges, which contains all our associates, the number of new edges is $\le\frac{|V|-1}{2}$, giving us the total $$|E|\le\frac{|V|-1}{2}+|V|-1=\frac{3(|V|-1)}{2}$$

New edges cannot share common associates, so each new edge has a completely unique pair of associates.

During the training session, someone showed me yet another idea, to consider the bridges of the graph. He hoped to show the existence of a bridge (an edge that would divide the graph into separate components if removed) and induct. Unfortunately, the graph may not have any bridges. However, he proved that if the graph does not have any bridges, it must satisfy a very constrained structure that looks like a "tree of triangles" which gives him the desired bound.

I liked the idea very much but was hoping for there to be a cleaner way to finish the solution. After a night's rest, I came up with the following:

Solution 3: Bridges Firstly, note that it suffices to prove the statement for connected graphs. To see this, suppose our graph has connected components with sizes $V_1,V_2,...V_k$. If we manage to prove the problem statement for all connected graphs, we have the bound $$|E|\le\frac{3(|V_1|-1)}{2}+\frac{3(|V_2|-1)}{2}+...+\frac{3(|V_k|-1)}{2}=\frac{3(|V|-k)}{2}\le\frac{3(|V|-1)}{2}$$

Now we may turn our attention to connected graphs. Consider an edge of the graph, $v_1v_2$. If it is a bridge, then by definition, when we remove the edge, it splits the graph into $2$ connected components $A_1,A_2$. Again we may proceed by induction. $|V|=1,2,3$ are obvious. By induction we have $$|E|\le\frac{3(|A_1|-1)}{2}+\frac{3(|A_2|-1)}{2}+1=\frac{3(|V|-1)}{2}-\frac{1}{2}$$

Otherwise, if the edge is not a bridge, then there exists another path from $v_1$ to $v_2$. However, this forms a cycle with the edge $v_1v_2$, so it must be a cycle of length $3$, $v_1v_2v_3v_1$. Suppose there was a path from $v_1$ to $v_3$ not using any of these $3$ edges. Then the path has at least length $2$ and adding the edges $v_1v_2$ and $v_2v_3$ would form a cycle of length $\ge 4$, contradiction!

Therefore, when we remove the $3$ edges, there is no path from $v_1$ to $v_3$. Similarly there is no path from $v_1$ to $v_2$ and from $v_2$ to $v_3$. This means that $v_1$,$v_2$,$v_3$ are in separate components now! Let these be $A_1,A_2,A_3$, then by induction, $$|E|\le\frac{3(|A_1|-1)}{2}+\frac{3(|A_2|-1)}{2}+\frac{3(|A_3|-1)}{2}+3=\frac{3(|V|-1)}{2}$$

If we have a cycle, it is of length 3 and splits the graph apart into 3 connected components.

Additional Remarks

Note that the ideas of maximal path and spanning trees work so well because they are in some sense a maximal acyclic structure.

I love such a problem where multiple different ideas can all lead to nice solutions. I make it a point to showcase different approaches when I conduct trainings because it leads to more instructive value per problem. After all, getting acquainted with different approaches is crucial to developing a holistic skillset that can tackle a wide variety of problems.

It is possible to adopt a mindset of only learning a new method when a question absolutely requires it, but then such a question could be so complex that it is difficult to use it for learning a new approach. I believe it is more productive in the long run to gain exposure to new techniques using problems where the ideas apply in a relatively straightforward manner, even if you already know that the problem can be solved by other means.