Si el borde $xy$ es un puente de $G$ alors $x$ y $y$ están en componentes separados de $G$ - $xy$ .
No se me ocurre ningún contraejemplo, así que tengo la impresión de que se puede demostrar. ¿Cómo se aborda esta prueba? ¿Se puede hacer asumiendo $G$ tiene un vértice de corte y luego mostrar una contradicción?
Un puente es una arista cortada. Así que $G - xy$ separa $G$ en dos componentes separados. Así que $x$ debe estar en un componente y $y$ en el otro. Queremos utilizar el hecho de que una arista es un puente si y sólo si no está contenida en ningún ciclo de $G$ .
Podrías demostrarlo por contradicción. Supongamos que $xy$ es un borde de corte pero $x, y$ están en el mismo componente de $G - xy$ . Entonces existe un $x-y$ en un componente de $G - xy$ . Así que $G$ tiene al menos dos $xy$ caminos. Así, $xy$ está contenida en un ciclo de $G$ , contradiciendo el hecho de que es un puente.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
