# What graph with 7 vertices that doesn't contain $K_3$ as subgraph has the maximal number of edges?

is there graph with vertices 7 that not contain $$K_3$$ as subgraph and have biggest edge?

is this question trying to ask to remove all triangle in K7 graph?

for this problem , is this possible to solve like this

$$\frac{7.6}{2}-\frac{3.2}{2}=18 edges$$ but ofourse it contain triangle(?) here is the possible graph that i can think of..

edit: i think once again that, biggest one is bipartite graph, such as $$K_{3,4}$$ with 12 edges and 7 vertices .(?)

• It's unclear what you are asking. Are you asking what is the maximal possible number of edges for a graph on 7 vertices that doesn't contain $K_3$ as a subgraph? – Randy Marsh Nov 20 '19 at 3:56
• @GoranMalic yes! i think its $K_{3,4}$.. – fiksx Nov 20 '19 at 3:57

Indeed, $$K_{3,4}$$ is correct.
To prove this, let's solve for $$n$$ vertices.
First note that any bipartite graph is triangle-free (as it's an odd length cycle).
I'll show that the graph with the most edges is bipartite:

Let $$G = (V,E)$$ be a triangle-free graph such that $$|V|=7$$ and let $$v\in V$$ such that $$\deg_G(v)=\varDelta_G$$, the vertex with the highest degree in $$G$$.
Create the following bipartite graph $$H=(L,R,E{'})$$:
$$L=N_G(v)$$, the set of neighbors of $$v$$, $$R=G/N_G(v)$$, $$E^{'}=\{(v_i,u_i)|v_i\in L,u_i\in R\}$$, i.e., the complete bipartite graph between the neighbors of $$v$$ to the rest of the vertices.
Now, let $$u\in V$$ be a vertex in $$G$$. If $$u\in N_G(v)$$ then $$\deg_H(v)=|N_G(v)|=\deg_G(v)\ge \deg_G(u)$$.
If $$u\notin N_G(v)$$ then $$\deg_G(v)\le |V/N_G(v)|$$ as $$u$$ can't be connected to another vertex in $$N_G(v)$$ for it would create a triangle. But, $$\deg_H(v)=|V/N_G(v)|$$ so $$\deg_H(u)\ge \deg_G(u)$$.

We got that for each vertex $$u\in V$$ it holds that $$\deg_H(u)\ge \deg_G(u)$$, so $$E(H)=\frac{\sum_{u\in V} {\deg_H(u)}}{2}\ge \frac{\sum_{u\in V} {\deg_G(u)}}{2} = E(G)$$

As we got that every triangle-free graph has a bipartite graph with at least as many edges, it is sufficient to take the bipartite graph with $$n$$ vertices with the highest number of edges.

So the biggest graph is obviously of the form $$K_{k,l}$$ where $$k+l=n$$. Let $$\alpha$$ be the unique number such that $$k=\frac{n}{2} +\alpha, l=\frac{n}{2}-\alpha$$ and we got that the number of edges is $$\frac{n^2}{2}-\alpha^2$$ so to maximize it we must choose $$\alpha = 0$$ when $$n$$ is even and $$\alpha = \frac{1}{2}$$ when $$n$$ is odd, and the number of edegs is $$\lfloor \frac{n^2}{4} \rfloor$$.

If we let $$n=7$$, we get that the maximal graph is indeed $$K_{\frac{7}{2} + \frac{1}{2}, \frac{7}{2}-\frac{1}{2}}=K_{4,3}$$ with $$12$$ edges.

• thankyou so much!! in order to proof this do you learn this in undergraduate or master?? – fiksx Nov 20 '19 at 9:45
• I learned it in an undergrad graph theory course – Asaf Rosemarin Nov 20 '19 at 10:09
• @fiksx You can prove that equality of the upper bound given in Mantel's theorem on the number of edges in a triangle-free graph is achieved by $K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}$, which most would probably see in an undergraduate intro course (This appears early on in Doug West's Intro to Graph Theory text). – Hendrix Nov 20 '19 at 14:14

You can prove that equality of the upper bound given in Mantel's theorem on the number of edges in a triangle-free graph is achieved by $$K_{⌊n/2⌋,⌈n/2⌉}$$, which most would probably see in an undergraduate intro course (This appears early on in Doug West's Intro to Graph Theory text).

This graph $$K_{\lceil n/2 \rceil, \lfloor n/2 \rfloor}$$ has a name: the Turán graph. You can read more about it here.