3
$\begingroup$

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

enter image description here

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ – Randy Marsh Nov 20 '19 at 3:56
  • 1
    $\begingroup$ @GoranMalic yes! i think its $K_{3,4}$.. $\endgroup$ – fiksx Nov 20 '19 at 3:57
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ thankyou so much!! in order to proof this do you learn this in undergraduate or master?? $\endgroup$ – fiksx Nov 20 '19 at 9:45
  • $\begingroup$ I learned it in an undergrad graph theory course $\endgroup$ – Asaf Rosemarin Nov 20 '19 at 10:09
  • 1
    $\begingroup$ @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). $\endgroup$ – Hendrix Nov 20 '19 at 14:14
0
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$

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.