Graph Theory: Extremal Problem

Mellete
Messages
2
Reaction score
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:
Physics news on Phys.org
Still having trouble showing that there is a vertex with degree less or equal to δ(Tr(p))
 
Prove $$\int\limits_0^{\sqrt2/4}\frac{1}{\sqrt{x-x^2}}\arcsin\sqrt{\frac{(x-1)\left(x-1+x\sqrt{9-16x}\right)}{1-2x}} \, \mathrm dx = \frac{\pi^2}{8}.$$ Let $$I = \int\limits_0^{\sqrt 2 / 4}\frac{1}{\sqrt{x-x^2}}\arcsin\sqrt{\frac{(x-1)\left(x-1+x\sqrt{9-16x}\right)}{1-2x}} \, \mathrm dx. \tag{1}$$ The representation integral of ##\arcsin## is $$\arcsin u = \int\limits_{0}^{1} \frac{\mathrm dt}{\sqrt{1-t^2}}, \qquad 0 \leqslant u \leqslant 1.$$ Plugging identity above into ##(1)## with ##u...
Back
Top