So I have to prove by induction in the number of the vertices of the graph this sentence:
Let r$\ge$ 2.
i)Use (strong) induction in the number of vertices to prove that, for n$\ge1$ every ( simple non- directed) graph that does not contain K$_{r+1}$ ( complete graph with (r+1) #vertices) , has no more than
$(r-1)n^2 /2r$ edges.
ii) Prove that there exists a graph , with kr vertices , that does not contain K$_{r+1}$, as a subgraph.
Okay so the idea is this:
- Base If n = 1 , then the graph obviously does not contain Kr+1 as a subgraph and it is easy to show that the formula is true if n =2 the same
Induction hypothesis
Suppose it is true for every graph with n = k $\le$ r
Induction Step
we will prove that it is true for a graph with n = k + 1 , vertices
Proof) We can , make two different vertices teams , one with (n -r) vertices and another one with r vertices. Since $(n -r) = k + 1 -r < r$ and $r $\le$ r$ , in both teams we can use the induction hypothesis , and find the maximum number of edges between their vertices.For the team with (n-r) it is no more than : $(n-r)^2(r-1)/2r$ edges and for the team with r vertices it is no more than $r^2(r-1)/2r$ edges. My problem , is when I think about the edges among vertices of the two teams . How I make sure , that these edges do not create Kr+1? Since I supposed in the Induction Hypothesis , that k$\le$r $=>$ k+1$\le$