1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Graph Theory: Extremal Problem

  1. Apr 7, 2014 #1
    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. jcsd
  3. Apr 8, 2014 #2
    Still having trouble showing that there is a vertex with degree less or equal to δ(Tr(p))
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted