# Triangle free graph with $n$ vertices and maximum degree $k$ has at most $k(n-k)$ edges.

Having a graph $$G$$ which is simple and non-directed with $$n$$ vertices and max degree of a vertex $$k$$. Then show if it does not contain $$K_3$$ as induced subgraph then that proves $$|E(G)|\le (n-k)k$$

So,having to find an upper limit to the number of edges. My thoughts so far are:

1)If it does not contain an induced subgraph of $$K_3$$ then it does not have any kind of bigger $$K$$ and then the degree of $$k$$ is $$2$$.

Extra thought(not complete):Having a vertex ν that is $$k(=2)$$ degree then compute the sum of degrees $$V(G)-N(v)$$. [$$N(ν)$$ is neighbourhood of $$v$$].I need some analysis if correct to this last statement.

• Note that this does not imply that $k = 2$, since you can have (for example) a star graph. Mar 21, 2019 at 21:29
• The degree can be much larger than 2 though. Consider for $n$ even and arbitrarily large the graph $K_{n/2,n/2}$. Every vertex has degree $n/2 >> 2$. It however does have no more than $n/2*(n-n/2)$ edges...
– Mike
Mar 21, 2019 at 22:04

Let $$v$$ be a vertex of degree $$k$$. Then every vertex $$u \in N_G(v)$$ cannot have a neighbor in $$N_G(v)$$ lest there be a triangle. So each such $$u$$ can have degree at most $$N-k$$; and there are $$k$$ such $$u$$. Every vertex $$w \not \in N_G(v)$$ [which includes $$v$$ itself] can have degree at most $$k$$ by the hypothesis that $$G$$ has maximum degree $$k$$; there are $$N-k$$ such $$w$$.

So $$|E(G)| = \frac{1}{2} \times \left(\sum_{u \in N_G(v)} d_G(u) + \sum_{w \not \in N_G(v)} d_G(w) \right)$$

$$\le \frac{1}{2} \times \left(k \cdot (N-k) + (N-k)\cdot k\right)$$

which gives the desired bound.

• I think your point (2) is not quite right. When $k=N-1$, then your linked answer implies a triangle free graph has at most $N^2/4$ edges, but this is not enough to show it has at most $k(N-k)=N-1$ edges. Mar 21, 2019 at 23:30
• You are correct @MikeEarnest I just fixed
– Mike
Mar 22, 2019 at 0:18
• Sweet proof! :D Mar 22, 2019 at 0:27
• Thank you @MikeEarnest!
– Mike
Mar 22, 2019 at 1:21