Calculate the maximum number of edges of a graph without two disjoint $K_3$

665 Views Asked by At

Let $G$ be a simple graph without two disjoint $K_3$ (no common vertices). What is the maximum of $|E(G)|$ in terms of the number of vertices $n$ of $G$?

If $G$ is a graph without a $ K_3$ , I get the result by using Turán's theorem. But how to solve it when we do not allow two disjoint $K_3$?

2

There are 2 best solutions below

0
On

Denote the asked maximum by $e$. We can obtain rather tight bounds for $e$ as follows. A complete tripartite graph $K_{s,t,1}$ where $|s-t|\le 1$ gives a lower bound $$e\ge\left\lfloor \frac 14(n-1)^2\right\rfloor+n-1=\left\lfloor \frac 14(n^2+2n-3)\right\rfloor.$$ On the other hand, if $n\ge 3$ we remove from $G$ any triangle then the remaining graph will be triangle-free, so, by Turán’s Theorem, it has at most $\frac 14(n-3)^2$ edges. So $$e\le 3+3(n-3)+\frac 14(n-3)^2=\frac 14(n^2+6n-15).$$ I’ll try to improve the upper bound.

1
On

Let $f(n)$ be the maximum possible number of edges in a $2K_3$-free graph of order $n$,
i.e., a (simple) graph on $n$ vertices which does not contain two vertex-disjoint triangles.


Theorem. $f(n)=\binom n2$ for $n\le5$; $f(6)=12$; and, for $n\ge7$, $$f(n)=\left\lfloor\frac14(n^2+2n-3)\right\rfloor.$$


Proof. For $n=6$ note that $K_{1,1,1,3}$ is a $2K_3$-free graph with $6$ vertices and $12$ edges; on the other hand, it's easy to see that removing only $2$ edges from $K_6$ leaves two disjoint triangles intact.


From now on we assume $n\ge7$. By considering (as in Alex Ravsky's answer) a complete tripartite graph $K_{1,s,t}$ with $s=\left\lfloor\frac12(n-1)\right\rfloor$ and $t=\left\lceil\frac12(n-1)\right\rceil$, we see that $$f(n)\ge\left\lfloor\frac14(n-1)^2\right\rfloor+n-1=\left\lfloor\frac14(n^2+2n-3)\right\rfloor.$$


All that remains is to prove the upper bound $f(n)\le\left\lfloor\frac14(n^2+2n-3)\right\rfloor$ for $n\ge7$.
Let $G=(V,E)$ be a $2K_3$-free graph of order $n\ge7$ and clique number $\omega\le5$.


Case 1: $\omega\le2$. Then, by Mantel's theorem, $$|E|\le\frac14n^2\lt\frac14(n^2+2n-3).$$


Case 2: $\omega=3$. Then, since each vertex outside the $K_3$ has at most $2$ neighbors in the $K_3$, $$|E|\le\binom32+\frac14(n-3)^2+2(n-3)=\frac14(n^2+2n-3).$$


Case 3: $\omega=5$. Then, since each vertex outside the $K_5$ has at most one neighbor in the $K_5$, $$|E|\le\binom52+\frac14(n-5)^2+n-5=\frac14(n^2-6n+45)\lt\frac14(n^2+2n-3).$$


Case 4: $\omega=4$, and $G$ has no subgraph $K_{1,1,1,2}$. Since each vertex outside the $K_4$ is joined to at most $2$ vertices in the $K_4$, $$|E|\le\binom42+\frac14(n-4)^2+2(n-4)=\frac14(n^2+8)\lt\frac14(n^2+2n-3).$$


Case 5: $\omega=4$, and $G$ has a subgraph $K_{1,1,1,2}$. Then joining a vertex outside the $K_{1,1,1,2}$ to $4$ vertices in the $K_{1,1,1,2}$ would create either a $K_5$ or a $2K_3$; thus each vertex outside the $K_{1,1,1,2}$ has at most $3$ neighbors in the $K_{1,1,1,2}$, and so $$|E|\le9+\left\lfloor\frac14(n-5)^2\right\rfloor+3(n-5)=\left\lfloor\frac14(n^2+2n+1)\right\rfloor=\left\lfloor\frac14(n^2+2n-3)\right\rfloor+1.\tag{*}$$


To finish the proof, I have to show that the upper bound in Case 5 can not be attained. Assume for a contradiction that equality holds in $(^*)$. Then each vertex outside the $K_{1,1,1,2}$ has $3$ neighbors in the $K_{1,1,1,2}$, and there are $\left\lfloor\frac14(n-5)^2\right\rfloor$ edges outside the $K_{1,1,1,2}$. Since $n\ge7$ we have $\left\lfloor\frac14(n-5)^2\right\rfloor\ge1$, so we can choose two adjacent vertices $x,y$ outside the $K_{1,1,1,2}$. Since $x$ and $y$ each have $3$ neighbors in the $K_{1,1,1,2}$, they have a common neighbor $z$ in the $K_{1,1,1,2}$, forming a triangle $xyz$. But the $K_{1,1,1,2}$ contains a triangle disjoint from $xyz$, contradicting our assumption that $G$ is $2K_3$-free.


Extremal graphs. By an extremal graph of order $n$, I mean a $2K_3$-free graph on $n$ vertices with the maximum possible number of edges. The complement of a graph $G$ is denoted by $\overline G$.

For $n\le5$ the only extremal graph is $K_n$.

For $n=6$ the only extremal graph is $K_{1,1,1,3}$.

For $n=7$ there are three extremal graphs: $K_{1,1,1,4}$, $\overline{K_3+K_{1,3}}$, and $K_{1,3,3}$.

For $n=8$ there are two extremal graphs: $\overline{K_4+K_{1,3}}$ and $K_{1,3,4}$.

For $n\ge9$ the only extremal graph is $K_{1,s,t}$ where $s=\left\lfloor\frac12(n-1)\right\rfloor$ and $t=\left\lceil\frac12(n-1)\right\rceil$.