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.
vertex independent set and the maximal clique
user40096
- 421
- 2
- 13