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.
First replace the problem with graph theoric concepts:
Assume a graph $G$ without cycles of length $4$ or more prove that $e \le \frac{3n-3}{2}$.
Consider the spaning tree of the graph adding each edge will create a new cycle which should be of length $3$ and these cycles shouldn't share a edge since then we will have a cycle of length $4$.Adding any edge will consume $2$ edges of the spaning tree.so we can have at most $\lfloor \frac{n-1}{2} \rfloor$ more edges and the problem is solved.
Nice problem! I used this as training material for students in Singapore, I thought the ideas were quite instructive.
I commented about this and provided 2 other solutions in my blog post
https://simoxmenblog.blogspot.com/2024/04/a-nice-story-problem-from-germany-i.html