Does a graph contain a 3-cycle or a 4-cycle 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?

Divide the group in half.  The fifty people in one half must each know at least 20 people in their half.  The maximal girth 5 cage graph for 50 vertices is the Hoffman-Singleton graph, with degree 7.  
If each person knows more than 57 people, a 3 or 4 cycle is also forced.
