¿Cuál es la forma más fácil de demostrar que el vértice v es un vértice cortado en un gráfico conectado G si y solo si existen 2 vértices x e y en G, de modo que cada camino entre x e y pase por v?

Answer 1

Esta pregunta se puede responder fácilmente desde la definición de un vértice cortado. Recuerde que [matemática] v [/ matemática] es un vértice cortado de un gráfico [matemática] G [/ matemática] si [matemática] c (G \ setminus v)> c (G) [/ matemática], donde [matemática] c (G) [/ math] denota el número de componentes de [math] G [/ math]. En particular, si [math] G [/ math] está conectado , entonces [math] v [/ math] es un vértice cortado de [math] G [/ math] si [math] G \ setminus v [/ math] es desconectado

Deje que [math] G [/ math] sea un gráfico conectado . Si [math] v [/ math] es un vértice cortado , entonces [math] G \ setminus v [/ math] tiene al menos dos componentes, por ejemplo, [math] G_1 [/ math] y [math] G_2 [/ math ] Elija cualquier [matemática] x \ en V (G_1) [/ matemática] y cualquier [matemática] y \ en V (G_2) [/ matemática]. Como [math] G [/ math] está conectado , debe existir al menos una ruta [math] xy [/ math] en [math] G [/ math]. Si alguna de las rutas [matemáticas] xy [/ matemáticas] en [matemáticas] G [/ matemáticas] no contiene [matemáticas] v [/ matemáticas], entonces la misma ruta conectará [matemáticas] x [/ matemáticas] y [ matemática] y [/ matemática] en [matemática] G \ setminus v [/ matemática], lo que implica que [matemática] x [/ matemática] y [matemática] y [/ matemática] se encuentran en el mismo componente de [matemática] G \ setminus v [/ math]. Esta contradicción muestra que cada ruta [math] xy [/ math] en [math] G [/ math] debe contener [math] v [/ math].

Por el contrario, suponga que [math] x, y \ en V (G) [/ math] tal que cada ruta [math] xy [/ math] contiene [math] v [/ math]. Luego, la eliminación de [math] v [/ math] desconecta claramente [math] x [/ math] y [math] y [/ math], de modo que [math] G \ setminus v [/ math] está desconectado. Por lo tanto, [math] v [/ math] es un vértice cortado de [math] G [/ math]. [matemáticas] \ blacksquare [/ matemáticas]