Demostrar que si existen dos caminos distintos de u a v,Existe un circuito simple

Question

Si existen al menos dos caminos distintos en el grafo desde u hasta v, entonces el grafo contiene un circuito simple.

He empezado por definir algunas cosas Un circuito simple es un circuito en el que, salvo el primer y el último vértice, que son iguales, no hay vértices repetidos.

Se dice que las dos trayectorias que parten de u y terminan en v son distintas si no tienen el mismo vértice interno en común o la misma arista interna en común.

Con la nueva información recibida, empezaría por suponer que este grafo contiene un circuito simple con vértices a,b,c,d,e,f tiene aristas ab,bc,cd,de,ea que conforman el circuito simple . donde a=U y d=V. Si sólo existiera un camino distinto, no habría ningún camino de vuelta desde d hasta a que diera un circuito simple, por lo que un grafo tendría que tener al menos dos caminos distintos para tener un circuito simple.

Me gustaría que mis pruebas fueran examinadas.

Answer 1

Creo que se está distrayendo con el último punto que ha mencionado. No lo necesitas. Puedes construir tu circuito simple a partir de los dos caminos distintos de $u$ a $v$ .

Dejemos que $p$ y $q$ sean caminos distintos desde $u$ a $v$ y que $\overline{q}$ sea la inversa de $p$ (así $\overline{q}$ va de $v$ a $u$ ). Entonces $p\overline{q}$ es un circuito. ¿Es un circuito simple?

Answer 2

En primer lugar, debes convencerte de que tu gráfico tiene un circuito: sigue un camino desde $u$ a $v$ y el otro para ir de $v$ volver a $u$ . Si estos caminos son distintos en el sentido que has definido, sin vértices o aristas internas en común, entonces el paath que acabamos de construir debería ser un circuito simple (¿por qué?). Incluso si tus caminos no son distintos, digamos que comparten algunos vértices pero no todos, o algunas aristas pero no todas, deberías ser capaz de localizar un circuito simple anotando el primer vértice o arista que los dos caminos tienen en común (que no sea $u$ o $v$ ).