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.

  • $\begingroup$ 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$? $\endgroup$
    – user40096
    Sep 28, 2013 at 10:29
  • $\begingroup$ 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. $\endgroup$
    – user40096
    Sep 28, 2013 at 13:58
  • $\begingroup$ one counter example for $N=2$ would be an odd cycle. For $N\ge 3$, I am not quite sure. $\endgroup$ Sep 28, 2013 at 14:42
  • $\begingroup$ @user40096: I overlooked the difference between $N$ and $N-1$. My earlier comments removed. $\endgroup$
    – Seva
    Sep 28, 2013 at 17:00

1 Answer 1


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.

  • $\begingroup$ 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! $\endgroup$
    – user40096
    Sep 29, 2013 at 2:00

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.