# Graph Theory: Extremal Problem

1. Apr 7, 2014

### Mellete

1. The problem statement, all variables and given/known data

Homework, from Modern Graph Theory by Bela Bollobas, section on extremals:

1. Suppose that G is a graph with n > r + 1 vertices and tr(n) + 1 edges.
(a) Prove that for every p with r + 1 < p <= n there is a subgraph H of G
with |H| = p and e(H) >= tr(p) + 1. [Hint: Try to copy the proof of Turan’s
Theorem. You may wish to write n = qr + x where 0 <= x < r, and consider
the cases x = 0, x = 1 and x > 2.]
(b) Prove that G contains two copies of Kr+1 with exactly r common vertices

2. Relevant equations

tr(n) − δ(Tr(n)) = tr(n − 1).
where tr(n) is the Turan number, Tr(n) the Turan graph, and δ(G) is the minimum degree of G

3. The attempt at a solution

Use a descending induction on p.

Assume there exists a subgraph of order p and size greater or equal to tr(p) + 1.
Identify a vertex v with deg(v) <= δ(Tr(p)) = p - roof(p/r)
Delete v and its incident vertices
Since tr(p) − δ(Tr(p)) = tr(p − 1) the result is a subgraph of order p-1 and size greater or equal to tr(p-1) + 1 as required.
The result follows by induction.

The crucial step is proving the existence of a suitable v, which I've no clue how to do.

Last edited: Apr 7, 2014
2. Apr 8, 2014

### Mellete

Still having trouble showing that there is a vertex with degree less or equal to δ(Tr(p))