5
$\begingroup$

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 !

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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:

enter image description here

$\endgroup$
2
$\begingroup$

If $\chi(G)=3$, the graph cannot contain any $K_4$ as a subgraph:

enter image description here

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:

enter image description here

$\endgroup$
  • $\begingroup$ Yes, $27$ is the maximum possible number of edges in a $K_4$-free graph on $9$ vertices; this is an instance of Turán's theorem. $\endgroup$ – bof Jun 24 '16 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.