graph theory(basic doubt,kenneth rosen) closed

Question

Q.1) for which value of n are these graph are bipartite??

a)$C_{N}$ (cycle graph having "n" vertices)

(b) $W_{N}$ (wheel graph having "n" vertices)

Comments

a) C_N (cycle graph having "n" vertices)

---

because in a wheel graph doesn't contain any independent sets

---

Cn will be bipartite iff n is EVEN.

Wn will not be bipartite for any n.

---

Only when n>3

Option a) satisfied

Answer 1

A graph is bipartite graph when it can be coloured using 2 colour such that no two adjacent vertex are of same colour.

For a- Cn will be bipartite when n is even as then starting at any vertex and colouring alternatively will satisfy above criteria. But when n is odd then we require 3 colours and thus is not bipartite.

For b- As Wn is a wheel one vertex is connected to all in a cycle thus we need more than 2 colour which voilates the criteria for bipartite graph.