bipartite-graphsdiscrete mathematicsgraph theory
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?
Assuming a path allows crossing the same edges and vertices:
We are given vertices $a$ and $b$. We know that the graph contains a cycle of odd length. Let $c$ be a vertex on that cycle. Further, since the graph is connected, there exist paths $a\rightarrow c$ and $c\rightarrow b$. If the total length of the path $a\rightarrow c \rightarrow b$ is even, we are done. If not then consider the path $a\rightarrow c \rightarrow (\text{odd cycle back to $c$}) \rightarrow b$.
The definition of bipartite graph at Wikipedia is:
... a bipartite graph ... is a graph whose vertices can be divided into two disjoint and independent sets $U$ and $V$ such that every edge connects a vertex in $U$ to one in $V$.
A bipartite graph doesn't need to be connected. It's fine to have $U$ and $V$ of any size (possibly even empty). We can also have any number of edges (possibly even zero).
Here's an example of a bipartite graph (with $U$ and $V$ indicated by vertex colors):
The graph drawn in the question is complete bipartite graph $K_{1,2}$, and we can highlight sets $U$ and $V$ as shown below:
Best Answer
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$)?