Draw a graph which is both cycle and complete and a graph which is cycle but not bipartite (Must use 2 different graphs)

226 Views Asked by At

Draw a graph which is both cycle and complete and a graph which is cycle but not bipartite (Must use 2 different graphs)

I can't seem to find the answer to this question. This is what I drew enter image description here
This graph is the answer to both graphs asked but I can't think of a second different one. And does a edge in a cycle graph only have 2 degrees or can it have more than 2?

3

There are 3 best solutions below

0
On

A cycle is not bipartite if and only if it is odd. Just use a cycle of length $5$.

Every vertex in a cycle has degree $2$.

0
On

A graph (in fact the only) which is both a cycle and complete is $3$-cycle or a triangle. A graph that is a cylce but not complete is a $2k+1$ cycle for any positive integer $k$.

Here are the two graphs desired:

enter image description here

2
On

As they told you, a cycle with $2k$ vertices is always bipartite.

But if you're wondering why, then you can simply distribute the "odd" vertices into a set $X$ and the "even" vertices into a set $Y$

i.e. $X=\{v_1,v_3,v_5,\cdots, v_{2k-1}\}$ and $Y=\{v_2,v_4,v_6, \cdots v_{2k}\}$ and that is a bipartite graph.