1
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ It can be much shorter: If $ij$ is an edge, how many common neighbours must $i$ and $j$ have? $\endgroup$ Commented Aug 18, 2013 at 15:03
  • $\begingroup$ Well, there are 98 nodes left. $i$ and $j$ have at least 69 connections to be made each. $98-69 = 29$. So $i$ or $j$ can only have 29 unique connections maximum. Hence, there are 40 common nodes between $i$ and $j$. Meaning that there is most certainly a 3-cycle, as I could pick any of those 40 common nodes to be the third person in the 3-cycle? $\endgroup$ Commented Aug 18, 2013 at 15:22
  • $\begingroup$ Exactly! (Except it's "at least 40" common neighbours; there might be more than 40.) $\endgroup$ Commented Aug 18, 2013 at 15:27
  • $\begingroup$ At the same time, since $i$ and $j$ have at least two ($40\ge2$) common neighbours $a,b$, we find a 4-cycle $iajb$ $\endgroup$ Commented Aug 19, 2013 at 14:51

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .