0
$\begingroup$

Please see edit.

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.

$\endgroup$
1
  • $\begingroup$ "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. $\endgroup$
    – Dániel G.
    Apr 22 at 7:50
2
$\begingroup$

"if $d(v) \geq \omega(G)$, then the subgraph contains a clique larger than the largest clique in the original graph"

Above statement is not true

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.

Graph with 6 nodes and 6 edges

$\endgroup$
2
  • $\begingroup$ Hmm, I see. Does the argument change in any way if we are given that the supergraph (original graph $G$) is an interval graph? $\endgroup$ Apr 22 at 8:04
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 22 at 8:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.