# vertex independent set and the maximal clique

Let $N>2$ be a positive integer and $G$ be a simple graph satisfies:

1. the maximal degree of $G$ is $N$
2. the clique number of $G$ is $N$.

I want to ask if there exists a vertex independent set $I$ in $V(G)$ such that for every $N$-order complete subgraph $H$ of $G$, the intersection of $I$ and $V(H)$ is not empty. If not, please give a counterexample.

• First,if $I$ is empty,$I$ does not satisfes "for every $N$ -order complete subgraph $H$ of $G$, the intersection of $I$ and $V$($H$) is not empty"!Second,as you said,if the intersection of $I$ and $V$($H$) is empty,how do you know the vertex in $I$ is not adjacent to any vertex of $H$? Sep 28 '13 at 10:29
• You did not see my question carefully!The maximal degree of $G$ is $N$,but for any $N$-order complete subgraph $H$ of $G$,the degree of every vertex of $H$ is $N$-1. Sep 28 '13 at 13:58
• one counter example for $N=2$ would be an odd cycle. For $N\ge 3$, I am not quite sure. Sep 28 '13 at 14:42
• @user40096: I overlooked the difference between $N$ and $N-1$. My earlier comments removed.
– Seva
Sep 28 '13 at 17:00

If $G$ is an odd cycle (as commented above), the answer is no. If it's an $(n+1)$-clique, it meets your degree condition but not your condition on the clique number. And if it's neither a clique nor an odd cycle, then by Brooks' theorem, it has an $n$-coloring, all of whose color classes are independent sets that meet every $n$-clique.
• My condition has "$N>2$",so $G$ is not an odd cycle.And for the rest of your answer,it is right,thank you very much! Sep 29 '13 at 2:00