Hola
Gracias por tus palabras. Sé que no todos los sábados respondés, así que te agradezco por tan detallada respuesta, Luis.
mmmmm…… vaya por delante en que estoy en esos casos en los que creo que un estudiante tiene algún bloqueo o duda sobre un problema, pero no tengo ni ideal de cuál es. De tu historial en el foro, puedo afirmar con toda seguridad que sabes lo que es una demostración por inducción.
No tengo claro, eso si, lo que sabes de Teoría de Grafos; pero la idea de este problema es absolutamente elemental (más allá de que si uno quisiera ponerse puntilloso con algún detalle formal quizá este pudiera dar un poco la lata; pero poco).
Sé lo que es inducción. No me gusta tener que usar palabras para hacer una demostración, y eso se empeora cuando toco los temas de grafos, autómatas, no me gusta, pero bueno forma parte de las matemáticas discretas.
¿No te pasa a veces que hay alguna rama de las matemáticas y un hilo nuevo que un usuario pregunta (o en clase, o en tu estudio de las matemáticas) que te parezca pesado, latoso, lioso y te deje sin muchas ganas de responder o estudiar pero que aun así sabés que tenés que entender? A mí me pasa con teoría de grafos, y lo peor de todo es que estudio Ingeniería en Sistemas y es bastante importante por el tema de los algoritmos y eso

.
¿Entiendes lo que es un árbol en teoría de grafos?¿Lo "visualizas"? En caso afirmativo debería de serte evidente que al final todas esas ramitas en que se va ramificando el árbol, terminan por acabar en algún momento dejando al final vértices sin más descendencia, vértices de grado uno.
Más o menos. O sea yo me imagino al árbol como un diagrama
perfectamente armado en donde claramente se ve el padre y los hijos, un vértice en la cima y sus descendientes. Pero no me gusta verlo cuando está desarmado, o sea cuando no se distingue claramente la línea sucesora. Y ahí me frustro.
¡No!. Eso sólo se da en los árboles, no en cualquier grafo. ¡Además es precisamente lo qué quieres demostrar!.
Ah, sí, es cierto, debería haber prestado más atención...
¡Qué \( |V|=|A|+1 \) significa exactamente que \( vértices(G)=aristas(G)+1 \)!. ¿Acaso habías entendido otra cosa?.
No, sólo no me esforcé en verlo.
Entonces la idea de probar eso por inducción es suponer que es cierto para árboles de \( n-1 \) vértices y a partir de ahí probarlo para árboles de \( n \) vértices (¡exactamente igual qué en cualquier demostración por inducción!).
En inducción (sobretodo aplicado a ecuaciones de recurrencia) se supone cierta la fórmula para \( n \) y se demuestra para \( n+1 \). ¿Da igual hacerlo así, y si la supongo cierta para \( n+54 \) y la demuestro para \( n+53 \) da igual?
Qusiera transcribir hipótesis y tesis inductivas para verlo un poco más claro:
Hipótesis: Con \( n=|V| \) tenemos \( |V|=|A|+1 \).
Tesis: Con \( n=|V|-1 \) tenemos \( |V|-1=|A|+1 \).
¿Lo que hiciste fue partir de \( |V|-1 \) y tratar de llegar a \( |A|+1 \) (como se hace habitualmente)? Sé que lo importante es lo que dijiste acá:
así que es natural intentar a partir de nuestro árbol original de \( n \) vértices construir otro árbol de \( n-1 \) vértices para poder usar el mecanismo de inducción.
¿Correcto?
Saludos