Skip to main content

Let N>2$N>2$ be a positive integer and G$G$ be a simple graph satisfies: (1)the maximal degree of G is N; (2)the clique number of G is N. I

  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$I$ in V(G)$V(G)$ such that for every N $N$-order complete subgraph H$H$ of G$G$,the the intersection of I$I$ and V(H)$V(H)$ is not empty,if. If not,please please give a counterexample.

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.

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.

Source Link
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.