Given a graph $\mathscr G$, that has 100 nodes each with a degree can you show that this graph contains a 3-cycle and/or a 4-cycle?
The graph in question represents 100 people at an event, and they each know $\ge 70$ people. I need to prove that there a 3 people there who know eachother. So I translated it to finding a 3-cycle in the graph.
I've approached it this way:
3 people know 70 people minimum. So any 3 nodes $n \in \mathscr G$ have $\sum deg(n)$$\ge$ $3*70$.
This means that these 3 people at least have $(3*70) – 100 = 110$ nodes in common. These nodes can be friends with 2 OR 3 persons.
This is where I'm not so sure anymore:
Suppose each node has only been counted twice. This means that 2 of the 3 persons should have $55$ nodes in common, which leaves out the 3rd person who knows $70$ other people.
If two people have $55$ nodes in common, they each have a minimum of $15$ unique nodes. This makes a total of $85$ nodes for the both of them.
So, $100 – 85 = 15$. This means that there are only 15 people who are still left unconnected. So, the third person should at least be connected to 55 other nodes too.
Worst case, 30 of these nodes are the unique nodes from person 1 and 2. So at least 25 nodes are connected to person 1, 2 and 3.
Which leads us to a contradiction that there is a 3-cycle.
Is this a valid proof?
Best Answer
Consider the following theorem:
Let $G = (V,E)$ be a simple graph. If $|E|>\frac{1}{4}\cdot |V|^2$, then $G$ contains a triangle.
Let us probe your problem: We know $|V|= 100$.
From $2 \cdot |E| = \sum_{v \in V} d(v) \geq \sum_{v \in V} 70 = 100 * 70 = 7000$ follows $|E| \geq 3500$.
Since $\frac{1}{4}\cdot |V|^2 = \frac{1}{4}\cdot 10000 = 2500$, it follows that your graph does contain a triangle.
As reference for this theorem (including its proof) see theorem 1.7 on page 12 in "Handbook of Combinatorics", Vol. 1, ISBN-10: 0262571722.