Wednesday, March 10, 2010

Here is a much simpler proof of a lemma of Kostochka that i translated from Russian and used.

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

Proof. Assume not and let Q = {Q_1, ..., Q_r} be a bad collection of maximum cliques with r minimal. Then r \geq 3 and X_Q is complete since it is connected and transitive. Put Z = Q - {Q_1}. Then X_Z is connected and hence by minimality \cup Z contains a universal vertex. In particular |\cup Z| \leq Delta + 1. Thus

|\cup Q| \leq |Q_1 - Q_2| + |\cup Z| \leq 2(Delta + 1) - omega < 2omega.

But then Hajnal gives a contradiction.

1 comment:

Anonymous said...

Nice dispatch and this enter helped me alot in my college assignement. Thanks you as your information.