MHB Prove Triangle-Free Graph w/ 2n/5 Degree is Bipartite

[anandvineet27]

In a group of $$n$$ people, each pair are friends or strangers. No set of three people are mutually friends. For any partition of the $$n$$ people into two groups, there exists two people in a group that are friends. Prove that there exists a person who is friends with at most $$2n/5$$ people in the group.
Suppose not.
Consider a vertex . Let the set of its adjacent vertices be A and strangers be B. Clearly A has more than $$2n/5$$ members. As the graph is triangle free , there no mutual friends in A.
Consider B.
Assume there are two mutual friends p and q in B. As every member of B also has more than $$2n/5$$ adjacent vertices, A must have at least $$4n/5 +2$$ vertices, meaning that B has less than $$n/5$$. Now, every member of A has more than $$2n/5$$ adjacent vertices outside A. But clearly this is not possible.
Is there a flaw in the above argument? I seems a little simplistic to me.

 

[caffeinemachine]

I don't see how the following is true.

As every member of B also has more than $$2n/5$$ adjacent vertices, A must have at least $$4n/5 +2$$ vertices...

May be this is a mistake.

 

[anandvineet27]

I don't see how the following is true.
May be this is a mistake.

It does look incorrect, not sure what i was thinking.

 

[Opalg]

In a group of $$n$$ people, each pair are friends or strangers. No set of three people are mutually friends. For any partition of the $$n$$ people into two groups, there exists two people in a group that are friends. Prove that there exists a person who is friends with at most $$2n/5$$ people in the group.

Using the title of the thread rather than phrasing the problem in terms of groups of friends, we want to show that a triangle-free graph with $n$ vertices where every vertex has degree $> 2n/5$ is bipartite. Equivalently, a triangle-free non-bipartite graph with $n$ vertices must have a vertex with degree $\leqslant 2n/5$.

If the graph $G$ is not bipartite then it must contain a cycle of odd order. If the shortest such cycle has length 7 or more, then (calling its vertices 1,2,3,... in consecutive order) we can add an extra edge by joining vertex 1 to vertex 4. In the new graph, there will still be no triangles, and each vertex will have at least as large a degree as in the original graph. But the new graph will contain a 5-cycle. So we may as well assume from the start that $G$ contains a 5-cycle.

View attachment 927​

Now start again. Suppose we have a graph that is triangle-free but contains a pentagon, with vertices labelled 1,2,3,4,5, and suppose that every vertex has degree at least $k$. Vertex 1 already has two neighbours (vertices 2 and 5), so it must have at least $k-2$ other neighbours (and these cannot include vertices 3 or 4, or we would have a triangle). Vertices 2 and 5 must also have at least $k-2$ other neighbours, and these must not include any of vertex 1's neighbours (or again we would have triangles). But vertices 2 and 5 might have some neighbours in common. Say there are $r$ vertices that are neighbours of both vertices 2 and 5. Then vertices 1, 2 and 5 together have at least $3(k-2) -r$ distinct neighbours.

Next, look at vertex 3. It cannot share any neighbours with vertex 2, but it can have the $k-2-r$ neighbours of vertex 5 that are not shared by vertex 2. Similarly, vertex 4 can have the $k-2-r$ neighbours of vertex 2 that are not shared by vertex 5. In addition, vertices 3 and 4 can share between them all the $k-2$ neighbours of vertex 1. That gives them a total of $3(k-2) -2r$ neighbours altogether. But they need $2(k-2)$ neighbours between them. So if $r>\frac12(k-2)$ then vertices 3 and 4 need $2r-(k-2)$ neighbours in addition to those taken up by vertices 1, 2 and 5.

There are now two separate cases to consider. First, if $r\leqslant \frac12(k-2)$ then vertices 1, 2 and 5 together have at least $\frac52(k-2)$ distinct neighbours. Adding in the 5 vertices in the pentagon itself, this means that $n\geqslant \frac52k$ ($n$ being the number of vertices in $G$). Therefore $k\leqslant \frac25n$.

The second case is when $r>\frac12(k-2)$. Then the five vertices of the pentagon require a total of $\bigl(3(k-2) -r\bigr) + \bigl(2r-(k-2)\bigr) = 2(k-2) + r$ distinct neighbours. This is again greater than $\frac52(k-2)$, so as before we get $k\leqslant \frac25n$.

 

[anandvineet27]

Yes, i had worked out a similar proof myself.
Turns out the result is infact a well known theorem (refer Wikipedia)

 

[Opalg]

Turns out the result is in fact a well known theorem (refer Wikipedia)

I assumed it must be, but the nearest thing I could find on Wikipedia was Turán's theorem. Can you give a link for this result?

 

[anandvineet27]

On the connection between chromatic number, maximal clique and minimal degree of a graph
see the proof of the first lemma.

 

[caffeinemachine]

Using the title of the thread rather than phrasing the problem in terms of groups of friends, we want to show that a triangle-free graph with $n$ vertices where every vertex has degree $> 2n/5$ is bipartite. Equivalently, a triangle-free non-bipartite graph with $n$ vertices must have a vertex with degree $\leqslant 2n/5$.

If the graph $G$ is not bipartite then it must contain a cycle of odd order. If the shortest such cycle has length 7 or more, then (calling its vertices 1,2,3,... in consecutive order) we can add an extra edge by joining vertex 1 to vertex 4. In the new graph, there will still be no triangles, and each vertex will have at least as large a degree as in the original graph. But the new graph will contain a 5-cycle. So we may as well assume from the start that $G$ contains a 5-cycle.

View attachment 927​

Now start again. Suppose we have a graph that is triangle-free but contains a pentagon, with vertices labelled 1,2,3,4,5, and suppose that every vertex has degree at least $k$. Vertex 1 already has two neighbours (vertices 2 and 5), so it must have at least $k-2$ other neighbours (and these cannot include vertices 3 or 4, or we would have a triangle). Vertices 2 and 5 must also have at least $k-2$ other neighbours, and these must not include any of vertex 1's neighbours (or again we would have triangles). But vertices 2 and 5 might have some neighbours in common. Say there are $r$ vertices that are neighbours of both vertices 2 and 5. Then vertices 1, 2 and 5 together have at least $3(k-2) -r$ distinct neighbours.

Next, look at vertex 3. It cannot share any neighbours with vertex 2, but it can have the $k-2-r$ neighbours of vertex 5 that are not shared by vertex 2. Similarly, vertex 4 can have the $k-2-r$ neighbours of vertex 2 that are not shared by vertex 5. In addition, vertices 3 and 4 can share between them all the $k-2$ neighbours of vertex 1. That gives them a total of $3(k-2) -2r$ neighbours altogether. But they need $2(k-2)$ neighbours between them. So if $r>\frac12(k-2)$ then vertices 3 and 4 need $2r-(k-2)$ neighbours in addition to those taken up by vertices 1, 2 and 5.

There are now two separate cases to consider. First, if $r\leqslant \frac12(k-2)$ then vertices 1, 2 and 5 together have at least $\frac52(k-2)$ distinct neighbours. Adding in the 5 vertices in the pentagon itself, this means that $n\geqslant \frac52k$ ($n$ being the number of vertices in $G$). Therefore $k\leqslant \frac25n$.

The second case is when $r>\frac12(k-2)$. Then the five vertices of the pentagon require a total of $\bigl(3(k-2) -r\bigr) + \bigl(2r-(k-2)\bigr) = 2(k-2) + r$ distinct neighbours. This is again greater than $\frac52(k-2)$, so as before we get $k\leqslant \frac25n$.

Hey Opalg.

You can have a simpler proof in case of a 5-cycle by observing that any vertex not in the five cycle can be adjacent with at most 2 vertices of the 5-cycle. Now pigeon hole principle settles the problem.

 

[Opalg]

Hey Opalg.

You can have a simpler proof in case of a 5-cycle by observing that any vertex not in the five cycle can be adjacent with at most 2 vertices of the 5-cycle. Now pigeon hole principle settles the problem.

Thanks.(Bow) I see now that what I was doing was just a long-winded pigeonhole argument.