Welcome to our community

Be a part of something great, join today!

To show that a triangle free graph where every vertex has degree > 2n/5 is bipartite

cupofcoffee

New member
Jun 5, 2013
7
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

Well-known member
MHB Math Scholar
Mar 10, 2012
834
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.
 

cupofcoffee

New member
Jun 5, 2013
7

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,725
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.

pentagon.png

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$.
 

cupofcoffee

New member
Jun 5, 2013
7
Yes, i had worked out a similar proof myself.
Turns out the result is infact a well known theorem (refer Wikipedia)
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,725

caffeinemachine

Well-known member
MHB Math Scholar
Mar 10, 2012
834
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.


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

MHB Oldtimer
Staff member
Feb 7, 2012
2,725
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.