- #1
Mellete
- 2
- 0
Homework Statement
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
Homework 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
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: