Camino más largo en el gráfico

Question

Tengo una pregunta general sobre la teoría de los grafos. Si tenemos que el grado mínimo de un nodo en el grafo es $\ge k$ que G tiene una longitud de trayectoria $\ge k$ . Ya he visto este ejemplo en este sitio, pero tengo una pregunta. Si suponemos que el camino más largo del grafo es de longitud r $v_0v_1\cdots v_r$ entonces $d(v_0)\ge k$ . Y cómo sabemos que cada vecino de $v_0$ ¿está dentro de este camino? Si conozco la definición de camino, entonces cada nodo tiene grado 1 o 2, así que si $k\ge 2$ esto no debería ser cierto, ¿verdad? Así que mi pregunta es cómo podemos saber que cada vecino de $v_0$ ¿está dentro del camino? PS, también he visto que si añadimos un nodo que no es vecino de $v_0$ entonces obtenemos un camino más largo que es una contradicción, pero de nuevo cómo podemos afirmar que si $k\ge 4$ entonces los 4 vecinos de $v_0$ están dentro de la ruta cuando sólo podemos tener 1 o 2 como grados de nodo en la ruta

Answer 1

Hay dos cosas que se pueden llamar caminos. Una es un gráfico de ruta , que es un gráfico que se parece a

v1 --- v2 --- v3 --- ... --- vn

en la que cada vértice tiene de hecho un grado $1$ o $2$ . Otro es un camino dentro de otro gráfico . Pueden definirse como una secuencia de vértices, o como una secuencia de vértices y aristas, pero siempre corresponden a subgrafos de su grafo original que son isomorfos al grafo del camino.

Así que si tienes un gráfico $G$ con un grado mínimo $k$ y has encontrado un camino más largo $P$ dentro de $G$ entonces $P$ nos da una subgrafo en el que cada vértice tiene grado $1$ o $2$ . Sin embargo, en $G$ en su conjunto, esos vértices tienen grado $k$ o más. Ni siquiera es necesariamente un subgrafo inducido: puede haber otras aristas entre los vértices del camino, que no forman parte del gráfico del camino.

Y eso es lo que ocurre cuando se mira este vértice $v_0$ en el camino $v_0, v_1, v_2, \dots, v_r$ . En el subgrafo de trayectorias tiene grado $1$ . En $G$ en su conjunto, tiene grado $k$ o más.

Si $v_0$ fuesen adyacentes a cualquier vértice que no estuviese en el camino, podríamos extender el camino. Esto es una contradicción si elegimos que el camino sea el más largo que existe.

Así que $v_0$ debe tener al menos $k$ vecinos en $G$ en su conjunto entre $\{v_1, v_2, \dots, v_r\}$ aunque sólo uno de ellos, $v_1$ es $v_0$ El vecino del en el subgrafo de caminos .