$(r+1)$ Clique of Induced subgraph and Turan’s theorem

360 Views Asked by At

$G$ is a $s$ regular graph.

$A$ is a set of vertices where $|A| = s$ and $A \subseteq G$.

$E$ is the number of edges of $G$.

$n$ is the total number of vertices of $G$.

Problem: Find the lower bound of $E$ so that induced graph $G-\{A\} $ has a $(r+1)$ clique where $r>1$.

Proposed Solution: Turan’s theorem states that n-vertex simple graphs with no $(r + 1)$-cliques, then the number of edges

$E \leq (1 -\frac{1}{r}) \frac{n^2}{2}$

If

$E > (1 -\frac{1}{r}) \frac{n^2}{2}$

Then for that particular $G$ with such $E$, ensures, for any arbitrary $A$ , $G-\{A\} $ has a $(r+1)$ clique where $r>1$.

Question: 1. Is the proposed solution correct?

  1. Is the proposed solution ‘rigorous’?

  2. Is there an alternative way to prove (also the case if the proof is incorrect)?