# Not sure how to connect the Pigeonhole principle to maximal clique size in finite graphs

I am currently stuck at a proof where to my understanding the key step is to argue how the fact that if in a subgraph, the degree of each vertex is at least the size of the largest clique in the graph $$G$$, $$d(v) \geq \omega(G), v \in V(G)$$, then the original assumption of ... is false. My guesses are that

1.) the contradiction is something like: "if $$d(v) \geq \omega(G)$$, then the subgraph contains a clique larger than the largest clique in the original graph".

2.) contradiction can be constructed somehow with pigeonhole principle from the fact that i.) the vertex set $$V(G)$$ is finite, ii.) self-loops are not allowed, iii.) each vertex $$v$$ is connected to $$\omega(G)$$ other vertices.

My current problem is that I don't know how to argue about the contradiction in general. I can give a constructive argument about a single graph, in which the aforementioned facts lead to a contradiction, but I don't know whether this is enough to argue in general.

The constructive argument about a single graph is that suppose there are in total $$\omega(G) + 2$$ nodes. Partition the nodes as $$T_1 = \{r\}, T_2 = \{v_1, v_2,\dots,v_{\omega(G)}\}, T_3 = \{e\}$$. Let the root node $$r$$ to be connected to all nodes in $$T_2$$. Connect all nodes in $$T_2$$ other than $$v_1, v_2$$ to each other. Then connect $$v_1$$ to all nodes in $$T_3 \cup T_2 \setminus \{v_2\}$$, and $$v_2$$ to $$T_3 \cup T_2 \setminus \{v_1\}$$. Now $$d(x) = \omega(G), x \in T_1 \cup T_2$$. But now, if $$e$$ is connected to the required remaining $$\omega(G) - 2$$ nodes there exists a clique with size $$\omega(G) + 1$$, which is a contradiction.

Edit: The graph $$G$$ is an interval graph.

• "if $d(v)\geq \omega(G)$, then the subgraph contains a clique larger than the largest clique in the original graph" - you won't get this in general: there are graphs with arbitrarily large minimum degree which do not even contain a triangle (i.e. for which $\omega(G) = 2$), for example complete bipartite graphs. Apr 22 at 7:50

"if $$d(v) \geq \omega(G)$$, then the subgraph contains a clique larger than the largest clique in the original graph"
Counterexample: Please see the below graph. It contains a subgraph $$\{1,2,3\}$$, where the degree of each node is $$4$$, i.e. larger than the maximum clique size in the original graph, but the graph G does not have clique larger than size 3.
• Hmm, I see. Does the argument change in any way if we are given that the supergraph (original graph $G$) is an interval graph? Apr 22 at 8:04
• Ok Consider graph on intervals in [0,2]. $I_0 = [0,1],I_1=[1,2]$ which intersect. Now let $I_{2i} = [1-\frac{1}{2i},1-\frac{1}{2i+1}]$ and $I_{2i+1} = [1+\frac{1}{2i+1},1+\frac{1}{2i}]\quad \forall i \in[1,\infty)$. Then degree of $I_0$=degree of $I_1 = \infty$. But max clique size is still 2. Apr 22 at 8:22