Un gráfico máximo conectado GGG sin ciclos de longitud de al menos k+1k+1k+1 tiene |V(G)|≤k|V(G)|≤k|V(G)| \leq k o tiene un vértice cortado cuando k≥2k≥2k \geq 2

¿Es cierto lo siguiente?:

Un gráfico máximo$G$sin ciclos de duración al menos$k+1$tiene$|V(G)| \leq k$o tiene un vértice cortado cuando$k \geq 2$.

Aquí máximo se entiende que no se puede agregar ningún borde a$G$sin introducir un ciclo de duración de al menos$k+1$, suponemos también que$G$está conectado. Nota bene: la declaración podría no ser cierta, pero por prueba y error sospecho que lo es.

Obviamente, cuando$|V(G)| \leq k$tal grafo maximal es el grafo completo$K_{|V(G)|}$que no tiene vértice cortado.

Asumir que$|V(G)| > k$y eso$G$no tiene ciclos de duración al menos$k+1$y es máxima. quiero mostrar eso$G$contiene$K_k$como un subgrafo inducido. Entonces, uno de los vértices de este$K_k$debe ser un vértice de corte.

Por el teorema de Menger, existe$u,v\in V$tal que hay dos caminos disjuntos$P_1$y$P_2$de$u$a$v$. tenemos eso

$$\begin{equation} |P_1| + |P_2| - 2\leq k, \end{equation}$$ dónde$|P_1|$cuenta el número de vértices en$P_1$. Ahora quiero mostrar que el subgrafo inducido por$P:= V(P_1) \cup V(P_2)$es en realidad un gráfico completo. Creo que entonces puedo terminar el argumento. Entonces, suponga que falta algún borde entre$v_1 \in P_1$y$v_2\in P_2$. Como$G$es máxima, la suma de la arista$v_1v_2$crearía un ciclo$C$de longitud por lo menos$k+1$. Ahora bien, si este ciclo es completamente disjunto de$P \setminus \{v_1,v_2\}$, entonces podemos usar los dos caminos para encontrar un ciclo de al menos$k+1$en el gráfico$G$antes de agregar el borde.

Así que asume que$C$pasa por algunos vértices de$P$. Ahora no sé cómo terminar el argumento como$C$puede pasar por los vértices de$P_1$y$P_2$en cualquier orden cambiando de un lado a otro entre vértices en ambos caminos y no encontrándolos en orden. (Cómo) ¿Se puede terminar el argumento?

¡Gracias de antemano!