A slightly simpler proof of Kostochka's lemma. It avoids the need for one extra lemma.

For a collection of maximum cliques Q in a graph G, let X_Q be the
intersection graph of Q.

Lemma. If Q is a collection of maximum cliques in a graph G with
\omega(G) > 2/3 (\Delta(G) + 1) such that X_Q is connected, then \cap
Q \neq \emptyset.

Proof. Suppose not and choose a counterexample Q := {Q_1, ..., Q_r}
minimizing r.

Let A be a noncutvertex in X_Q and B a neighbor of A. Put Z := Q -
{A}. Then X_Z is connected and hence by minimality of r, \cap Z \neq
\emptyset. In particular, |\cup Z| \leq \Delta(G) + 1.

Hence |\cup Q| \leq |\cup Z| + |A - B| \leq 2(\Delta(G) + 1) -
\omega(G) < 2\omega(G). This contradicts Hajnal's lemma.

Conjecture 14 from my recent paper is false by some pretty easy examples.


However, i still think Conjecture 13 (which Conjecture 14 implies) is true.


static void Main()
{
  Func<int, int> w = t => (t + (t >> 31)) ^ (t >> 31);
  Func<int, int> r = t => -(-t >> 31);
  Func<bool> z = () => { Thread.Sleep(20);
                         return true; };
  Func<string, bool> a = s => { Console.Write(s);
                                return true; };
  Func<int, int, bool> b = null;
  b = (n, k) => k <= n && (Console.ForegroundColor =
                (ConsoleColor)(r(k & (n - k)) + 1))
                != null && a("8") && b(n, k + 1);
  Func<int, bool> c = null;
  c = n => a("".PadLeft(40 - w(n) / 2, ' ')) &&
           (b(w(n), 0) || true) && z() && a("\n") &&
           (w(n) < 75 || n < 0) && c(n + 1);
  Func<bool> d = null;
  c(0);
  d = () => (c(-75) || true) && d();
  d();
}


See more at Interesting Graphs.

The only 7-mule containing a K_7 minus an edge.

i proved this recently. It would be interesting to explicitly construct a sequence of graphs showing that t_0 does not exist instead of relying on P \neq NP.