2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Note that this does not imply that $k = 2$, since you can have (for example) a star graph. $\endgroup$ Mar 21, 2019 at 21:29
  • $\begingroup$ 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... $\endgroup$
    – Mike
    Mar 21, 2019 at 22:04

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 21, 2019 at 23:30
  • $\begingroup$ You are correct @MikeEarnest I just fixed $\endgroup$
    – Mike
    Mar 22, 2019 at 0:18
  • 1
    $\begingroup$ Sweet proof! :D $\endgroup$ Mar 22, 2019 at 0:27
  • $\begingroup$ Thank you @MikeEarnest! $\endgroup$
    – Mike
    Mar 22, 2019 at 1:21

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.