Grafos bipartitos pueden tener las siguientes propiedades?

Question

Sea G un grafo bipartito con al menos$3$ vértices. ¿Puede tener las siguientes propiedades al mismo tiempo?

• $1$) Cada vértice es comenzar vértice de algún camino de Hamilton.
• $2$) No contiene ningún ciclo de Hamilton.

Descubrí, que esto sólo es posible si el número de vértices es aún y si las particiones tienen el mismo tamaño. Mi conjetura es, que no hay grafo bipartito con las propiedades deseadas, pero no puede probarlo.

Answer 1

un gráfico bipartito es acíclico, todos los vértices de dos conjuntos deben tener al menos una conexión, el gráfico es de dos coloreable, tiene clara ventaja