Deje $G$ ser la división gráfica de $\{1,2,3,4,5,6,7,8,9,10,12,14,16\}$. Tiene un hamilton/euler camino?

Question

Dado un grafo G cuyos vértices son a $V = \{1,2,3,4,5,6,7,8,9,10,12,14,16\}$, y hay una arista entre dos vértices $w$ $j$ fib $w\neq j$ $w$ divide $j$ o $j$ divide $w$.

(I) $G$ tiene un camino de Hamilton?

(II) No $G$ tiene un camino de Euler?

Cualquier ayuda se agradece. Para (yo) me puse a buscar el camino, pero no podía encontrarlo, y traté de ver lo que son los dos más mínimo grados entre dos vértices adyacentes y traté de ver si es $\geq 13$, pero también que eso no suceda.

Answer 1

Euler camino es fácil. Aquí hay tres vértices con grado impar:

• 4 -> 1, 2, 8, 12, 16 (5 los vecinos)
• 10 -> 1, 2, 5 (3 los vecinos)
• 12 -> 1, 2, 3, 4, 6 (5 los vecinos)

Un gráfico puede tener un camino de Euler sólo si en la mayoría de los dos vértices tienen grado impar. Por lo tanto, el grafo no contiene un camino de Euler.

Ensayo-y-error le da a este Hamilton-ruta: $$9 \rightarrow 3 \rightarrow 6 \rightarrow 12 \rightarrow 4 \rightarrow 8 \rightarrow 16 \rightarrow 2 \rightarrow 10 \rightarrow 5 \rightarrow 1 \rightarrow 7 \rightarrow 14$$