¿Un grafo biconectado bipartito no hamiltoniano?

Question

Así que estoy tratando de encontrar un gráfico biconectado bipartito no hamiltoniano y esto es lo que he encontrado: http://i.imgur.com/thUI0tn.png No hay ningún ciclo hamiltoniano y podemos dividir los vértices en dos partes pares. Entonces, ¿se ajusta este gráfico a todas las propiedades y, si lo hace, cómo puedo demostrarlo porque tengo problemas para demostrar que está biconectado?

Answer 1

¿Por qué no? $(\{1,2,3,4,5\}, \{\{1,2\}, \{1,3\}, \{1,4\}, \{2,5\}, \{3,5\}, \{4,5\}\})$ ? (Esto es $K_{2,3}$ .) La biconexión es bastante fácil de ver. La bipartición es $\{\{1,5\},\{2,3,4\}\}$ . Para los ciclos hamiltonianos, a partir de $1$ , se completa un ciclo y luego se debe dejar $1$ para alcanzar el vértice restante y nunca puede volver a $1$ . El análisis de $5$ es el mismo. Para $2$ , primero hay que ir a $1$ (o $5$ que es el mismo bajo el reetiquetado " $1$ " $\leftrightarrow$ " $5$ "), entonces el análisis de $1$ se aplica.