Skip to main content

In addition to the literature mentioned in the other answers, one can try some arguments based on counting.

Let u$u$ and v$v$ be two of n$n$ vertices in a triangle free-free graph, and further assume they are distinct and connected by an edge, with degrees c$c$ and d$d$ and c$c$ at most d$d$. Then their neighborhoods are disjoint, so c - 1 + d - 1$c - 1 + d - 1$ is at most n-2$n-2$, giving $2\delta \leq n$.

It might be fun to recreate the $2n/5$ result: here is a start. Take an odd cycle from a non bipartite graph with minimal cycle length. If the cycle length is 7$7$ or greater, show that three vertices will produce either a triangle, a shorter odd length cycle, or a degree at most 2n/5$2n/5$. Try a similar analysis with a 5$5$-cycle. Enjoy!

In addition to the literature mentioned in the other answers, one can try some arguments based on counting.

Let u and v be two of n vertices in a triangle free graph, and further assume they are distinct and connected by an edge, with degrees c and d and c at most d. Then their neighborhoods are disjoint, so c - 1 + d - 1 is at most n-2, giving $2\delta \leq n$.

It might be fun to recreate the $2n/5$ result: here is a start. Take an odd cycle from a non bipartite graph with minimal cycle length. If the cycle length is 7 or greater, show that three vertices will produce either a triangle, a shorter odd length cycle, or a degree at most 2n/5. Try a similar analysis with a 5-cycle. Enjoy!

In addition to the literature mentioned in the other answers, one can try some arguments based on counting.

Let $u$ and $v$ be two of $n$ vertices in a triangle-free graph, and further assume they are distinct and connected by an edge, with degrees $c$ and $d$ and $c$ at most $d$. Then their neighborhoods are disjoint, so $c - 1 + d - 1$ is at most $n-2$, giving $2\delta \leq n$.

It might be fun to recreate the $2n/5$ result: here is a start. Take an odd cycle from a non bipartite graph with minimal cycle length. If the cycle length is $7$ or greater, show that three vertices will produce either a triangle, a shorter odd length cycle, or a degree at most $2n/5$. Try a similar analysis with a $5$-cycle. Enjoy!

Source Link

In addition to the literature mentioned in the other answers, one can try some arguments based on counting.

Let u and v be two of n vertices in a triangle free graph, and further assume they are distinct and connected by an edge, with degrees c and d and c at most d. Then their neighborhoods are disjoint, so c - 1 + d - 1 is at most n-2, giving $2\delta \leq n$.

It might be fun to recreate the $2n/5$ result: here is a start. Take an odd cycle from a non bipartite graph with minimal cycle length. If the cycle length is 7 or greater, show that three vertices will produce either a triangle, a shorter odd length cycle, or a degree at most 2n/5. Try a similar analysis with a 5-cycle. Enjoy!