0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Adam Lowrance Dec 7 '17 at 18:45
0
$\begingroup$

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$.

$\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.