Let $G$ be simple undirected graph with degree of every vertices is at least 5. Prove or disprove that $G$ contains subgraph $K_4$.
I came up with this question when I were trying to find Ramsey number $R(4,3)$. I think my conjecture is correct but I am unable to prove it. If anyone have any idea please share with me. Thank you in advance !
Best Answer
The complete tripartite graph $K_{3,3,3}$ is a $6$-regular graph on $9$ vertices and has chromatic number $3$ so it contains no $K_4.$
By Turán's theorem, a simple graph with $9$ vertices and more than $27$ edges must contain $K_4$ as a subgraph, and $K_{3,3,3}$ (also known as the Turán graph $T(9,3)$) is the unique $K_4$-free simple graph with $9$ vertices and $27$ edges.