Hola
En general estoy desconcertado; porque todo lo que digo me parece obvio e intuitivo. No me refiero a los detalles técnicos que pudieran tener matices, me refiero a la idea global. Me gustaría que detallases más tus "no entiendo".
En ese sentido aunque primero he contestado a tus preguntas concretas al final he incluido otro ejemplo para intentar explicar mejor porque no me parece que esté bien la prueba de tu profesor. Casi me gustaría que te centrases primero en ese ejemplo antes que en lo demás.
1- Para probar una propiedad sobre árboles de \( n+1 \) vértices ves lícito comenzar con un árbol de \( n \) vértices y añadirle un vértice. Sin mayor justificación.
2- Para probar una propiedad sobre ciclos de orden \( n+1 \) NO ves lícito comenzar con un ciclo de orden \( n \) y añadirle un vértice. ¿Por qué?.
Si en algún momento en (1) y en (2) no usas que tiene de especial un árbol o un ciclo para justificar que tiene sentido una cosa si y la otra no. ¿Qué diferencia hay? ¿Una palabra a la que realmente no otorgas ningún significado?.
Está bien, entiendo que si no quiero probar (1) estaría "probando" (2), cuando sabemos que que (2) es falso. Entonces hay que probar (1)
No se...
. La frase que he marcado en rojo me resulta confusa. Entonces no se si he sabido transmitir bien la idea.
- Hay que justificar que todo árbol tiene un vértice \( v \) de grado \( 1 \).
Spoiler
Sea \( v_1\to v_2\to \ldots\to v_k) \) un camino maximal (no se puede añadir más vértices). Si \( v_1 \) no tiene grado \( 1 \), tiene otra arista distinta de la que lo une con \( v_2 \). Pero por ser un camino maximal \( v_1 \) no puede ser unido a otro vértice distinto de los \( k \) vértices que forman el camino por tanto estaría unido a alguno de los vértices \( v_3,\ldots,v_k \) y tendríamos un ciclo. Pero un árbol no tiene ciclos.
- Si quitas ese vértice \( v \) y su arista adyacente te vuelve a quedar un árbol.
Spoiler
Está claro que si el grafo original \( G \) no tenía ciclos al quitar un vértice de grado \( 1 \) y su arista, sigue sin haber ciclos. Lo único que hay que probar es que \( G-\{v\} \) sigue siendo conexo. Pero dados dos vértices de \( u,w\in G-\{v\} \) sabemos que se pueden conectar por un camino en \( G \). Como \( grado(v)=1 \) ese camino no puede contener a \( v \) (ya que en un camino salvo los vértices inical y final todos los demás tienen al menos grado dos). Por tanto ese camino está en \( G-\{v\} \).
No tengo claro que quieres decir con que no entiendes esa prueba. Te haré varias preguntas concretas.
1) ¿Entiendes que si a un árbol de \( n+1 \) vértices le quitas un vértice de grado \( 1 \) y la única arista adyacente lo que te queda es un árbol de \( n \) vértices?.
2) Entonces si cuando tenemos un árbol \( T_{n+1} \) de \( n+1 \) vértices somos capaces de quitarle uno y obtener un árbol \( T_n \) de \( n \) vértices...¡¿no es obvio que hemos probado que el árbol original \( T_{n+1} \) puede construirse añadiendo al árbol \( T_n \) de \( n \) vértices, el vértice que le habíamos quitado?!. ¿No es obvio que hemos probado que todo árbol de \( n+1 \) vértices se obtiene añadiendo un vértice a un árbol de \( n \) vértices?.
Claro, es lo único que falta probar en la demostración del profesor, porque en su prueba usa que un árbol de \( h+1 \) vértices se puede construir a partir de otro de \( h \) vértices agregándole un vértice. ¿Dónde habla de eliminar vértices?
La respuesta esto es el punto (2) del párrafo anterior. Soy yo y no tu profesor el que habla de eliminar vértices; e insisto en lo mismo, hablo de ello porque es la única forma que se me ocurre de justificar que todo de \( n+1 \) vértices se obtiene añadiendo un vértice a un árbol de \( n \) vértices.
Te voy a poner otro ejemplo más elaborado a ver si logro explicar mejor la crítica que hago a la prueba de tu profesor.
Definición: Un NO-árbol es un grafo conexo que tiene algún ciclo.
Spoiler
Vaya por delante que es una definición inventada. Pero eso es lo de menos. Es un nombre para un grafo con una determinada propiedad, sin más.
: Todo NO-árbol de \( 3 \) o más vértices tiene un ciclo de orden \( 3 \).
Prueba por inducción en el número \( n \) de vértices:Paso base: \( n=3 \). Si un NO-árbol tiene tres vértices como tiene que tener un ciclo y el ciclo más pequeño posible es de orden \( 3 \), entonces necesariamente el NO-árbol tiene un ciclo de orden \( 3 \).
Paso inductivo:
Hipótesis: En todo NO-árbol, si \( |V|=h\geq 3 \) entonces tiene un ciclo de orden \( 3 \).
Tesis: En todo NO-árbol, si \( |V|=h+1\geq 4 \) entonces tiene un ciclo de orden \( 3 \).
Para probarlo, consideremos cualquier NO-árbol \( G_h \) de \( h\geq 3 \) vértices, o sea \( V_h=\{v_1,v_2,\dots,v_h\} \). Sabemos por hipótesis que tiene tiene un ciclo de orden \( 3 \).
A cualquiera de esos NO-árboles, le agregamos un nuevo vértice \( v_{h+1} \) para formar un nuevo NO-árbol \( G_{h+1} \) es decir: \( V_{h+1}=V_u\cup\{v_{h+1}\} \).
Si no agregáramos arista alguna, dicho vértice queda aislado y el grafo no es conexo, no es NO-árbol. Por lo cual hay que agregar necesariamente una arista \( \{v_{h+1},v_i\} \) donde \( v_i \) es alguno de los vértices existentes en \( G_h \).
Una vez agregado el vértice y al menos una arista ya tenemos un grafo \( G_{h+1} \) conexo y con un ciclo de orden \( 3 \) (el mismo que tenía \( G_h \)). Por tanto \( G_{h+1} \)es un NO-árbol de \( h+1 \) vértices y hemos probado como queríamos que tiene un ciclo de orden \( 3 \), con lo cuál queda demostrada la tesis.
Obviamente la demostración NO puede estar bien, porque el Teorema que pretendía probar es FALSO. No es cierto que todo NO-árbol tenga un ciclo de orden tres. ¿Dónde está el error?.Saludos.
