Skip to content

6.11 Turan

Turan Theorem: The maximal possible number of edges of a graph on \(n\) vertices that does not have p-cliques is \(\leq(1-\frac{1}{p-1})\frac{n^2}{2}\)
The sharp bound is given by the Turan graphs and \(|n_i-n_j|\leq 1\) max

Denote the sharp bound by \(T_P(n)\)

  1. There are \(n\) batteries, of which \(k+1\) are good. You can test two batteries at a time by plugging them into a lamplight; the lamplight works only if both batteries are good. What is the minimal number of tests required to guarantee that the lamplight works?

    image connected if they are both good

    image​

    image​

  2. There are \(n\) people seated around a round table. In each move, two adjacent people swap seats. What is the minimal number of such swaps required to reverse the clockwise seating order of the people?

    image​

    image​

    image​

    image​

  3. There are \(4n\) points in the plane. Segments connect every pair of points that are exactly 1 unit apart. Given that every subset of \(n+1\) points contains at least one pair connected by a segment, prove that the total number of segments is at least \(7n\).

    image​

  4. Compute the chromatic polynomial for a) complete graph \(K_n\), b) cycle graph \(C_n\).

    image
    The first is complete graph

    image​

    ‍

‍