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

[anandvineet27]

In a group of \(\displaystyle n\) people, each pair are friends or strangers. No set of three people are mutually friends. For any partition of the \(\displaystyle 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 \(\displaystyle 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 \(\displaystyle 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 \(\displaystyle 2n/5\) adjacent vertices, A must have at least \(\displaystyle 4n/5 +2\) vertices, meaning that B has less than \(\displaystyle n/5\). Now, every member of A has more than \(\displaystyle 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 \(\displaystyle 2n/5\) adjacent vertices, A must have at least \(\displaystyle 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 \(\displaystyle n\) people, each pair are friends or strangers. No set of three people are mutually friends. For any partition of the \(\displaystyle 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 \(\displaystyle 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.