# What values of n lead to a modified cycle having a bipartite?

The graph $D_n$ is created by adding a vertex to $C_n$ and connecting the vertex to each of the vertices in $C_n$ with an edge. What values of n will lead to $D_n$ having a bipartite?

So far for my proof I have the following:

By definition of bipartite graphs, the vertex set of the graph must be partitioned into sets $V_1$ and $V_2$ where no members of either set share an edge. If the added vertex $v$ to $D_n$ connects to all of the vertices in $C_n$, the first partitioned set of $V$ will be $V_1$={$v$} because no edges can be shared between members of the same set. Thus, the set $V_2$ would be $V_2$={$v_1, v_2, ..., v_n$}. However, members of $V_2$ share edges so a bipartite can never be formed for any value of n.

Right? Wrong? Help?

• Your proof is correct. Alternatively, a graph is bipartite if and only if it contains no cycles of odd length. The graph $D_n$ has (many) $3$-cycles and so cannot be bipartite. – Adam Lowrance Dec 7 '17 at 18:45

## 1 Answer

Sounds right to me!

Since $C_n \subset D_n$ and $C_n$ isn't bipartite for $n \geq 3$, neither is $D_n$. And $C_n$ is only defined for $n \geq 3$.