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

Question

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 .(?)

Answer 1

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.

Answer 2

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).

Answer 3

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.