Skip to main content
1 of 2
user40096
  • 421
  • 2
  • 13

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.

user40096
  • 421
  • 2
  • 13