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:
Nice dispatch and this enter helped me alot in my college assignement. Thanks you as your information.
Post a Comment