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 !
On
If $\chi(G)=3$, the graph cannot contain any $K_4$ as a subgraph:
The above graph is just a $K_9$ with only $9$ edges removed, in particular a $K_{3,3,3}$, with chromatic number $3$, as clear from the picture (no couple of vertices with the same colour is joined by an edge, but the graph has plenty of embedded triangles).
On the other hand, it is not difficult to show that any graph on $9$ vertices with more than $27$ edges has a subgraph isomorphic to $K_4$. Quite disappointing and not even surprising, since a graph fulfilling such constraints is full of triangles and almost complete:
On
Clearly, since the sum of degrees across the 9 vertices must be even, there must be a vertex with degree at least $6$, meaning that only 2 vertices are isolated from this vertex. Choose the vertex of highest degree (degree-$6$ or higher) and label it as $A$ and the vertices connected it, the "linked set", as $\{B,C,D,E,F,G\}$. Each of these will have an additional minimum $4$ links to make in addition to the link to $A$, so at least $2$ of these in each case are within the linked set. So this gives 6 vertices and minimum 6 edges in the linked set, which can be connect as a ring to avoid triangles. Then the other two verrtices, $\{H,I\}$ can be connected to each point on the ring (but not to each other) to avoid any $K_4$.
A diagram of this:
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.