1
$\begingroup$

If you could explain the answer simply It'd help me out as I'm new to this subject.

For which values of n is the complete graph Kn bipartite? For which values of n is Cn (a cycle of length n) bipartite?

Is it right to assume that the values of n in Kn will have to be even since no odd cycles can exist in a bipartite? Also, for Cn is it correct that the length of the cycle will also need to be even since you need to take an even number of steps to travel from V1 to V2 and V2 back to V1?

$\endgroup$
  • $\begingroup$ For $K_n$, try drawing $K_3$ and $K_4$ to figure out why they aren't bipartite. And you are right about $C_n$. $\endgroup$ – Rocket Man Nov 11 '15 at 21:08
1
$\begingroup$

Hints. The question is whether you can partition the vertices such that each edge goes from a vertex in one part to a vertex in the other part. Equivalently, can you color each vertex red or black, so that no two vertices of the same color are neighbors (have an edge connecting them)?

Is it possible for $K_3$? Is it possible for $K_4$? Is it, in fact, possible for any $K_n, n > 2$? If a graph isn't bipartite, it is not a subgraph of any bipartite graph, either.

When is it possible for vertices arranged in a circle ($C_n$)?

$\endgroup$

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.