# A simple graph $G$ with even clique number, find a subset $A$ of the vertices, subgraph induced by $A,V-A$ have equal clique number

Given a simple graph $$G=(V,E)$$ s.t. $$2\mid \omega(G)$$,
Show that $$\exists S\subseteq V\text{ s.t. } f_G(S)=f_G(V\setminus S)$$
where $$f_G(A)$$ is the clique number of the sub-graph of $$G$$ induced by vertex set $$A$$.

I'm have trouble proving this property of clique number.
Several approaches have been tried but none leads to a correct proof.

• IDEA: Firstly, divide a largest clique $$C$$ of $$G$$ evenly into to subset $$A,B$$.
I want to continuously add vertices into $$A$$ and $$B$$ keeping the clique number of the sub-graphs induced by $$A,B$$ unchanged.
1. For every other vertex $$v$$, we have $$f(A\cup \{v\})=f(A)\lor f(B\cup \{v\})=f(B)$$, otherwise $$A\cup B\cup\{v\}$$ is a clique bigger than $$C$$.
2. After adding the first vertex, I can show that every other vertex $$v'$$ satisfy $$f(A\cup \{v'\})=f(A)\lor f(B\cup \{v'\})=f(B)$$ using the pigeonhole principle.
3. However, after adding $$|A|$$ vertices into $$A$$ or $$|B|$$ vertices into $$B$$, I can no longer have the property: $$f(A+v)=f(A)\lor f(B+v)=f(B)$$
• IDEA: Continuously find the largest clique $$C=\{v_1,\ldots v_k\}$$
if $$2\mid k$$ split it evenly, otherwise split it into $$\lfloor k/2\rfloor,\lceil k/2\rceil$$
This doesn't work, adding the vertices arbitrarily can cause unpredictable increase in clique number.
• other naive approaches.

I really need some hint to solve it.
btw, I don't know why the graph should be simple, I can't see a difference.

• BTW, I am also wondering if it is proper to post the same problem on math-stackexchange. I am familiar with the math site but not the CS site. – hehelego May 24 at 9:02
• This post is appropriate on CS.SE. It is not recommanded to cross-post on multiple SE sites. – Nathaniel May 24 at 10:01
• The pentagon is a counterexample to any approach that attempts to strictly reduce $\omega$: It has $\omega=2$, and so does either $G[S]$ or $G[V\setminus S]$ for all $S \subseteq V$. – j_random_hacker May 24 at 11:19
• After tons of searching and discussion. I find that this is exactly the problem 3 in IMO 2007. – hehelego May 24 at 14:59