15) Diga verdadero o Falso justificando la respuesta: a) Existe un árbol de 21 vértices y 19 aristas b) Si un grafo posee 21 vértices y 20 aristas...

a) Falso. Un árbol es un grafo no dirigido, conexo y sin ciclos. Para que un grafo tenga 21 vértices y 19 aristas, debe tener al menos un ciclo. Por lo tanto, no es un árbol.

b) Falso. Por el mismo motivo que en a).

c) Verdadero. Un árbol es un grafo no dirigido, conexo y sin ciclos. Para que un grafo con n vértices sea un árbol, debe tener n-1 aristas. Esto se debe a que si el grafo tiene n vértices, entonces tendrá n-1 pares de vértices. Cada par de vértices puede estar conectado por una arista, pero no todos los pares de vértices pueden estar conectados por una arista al mismo tiempo. Por lo tanto, el grafo tendrá n-1 aristas.

d) Verdadero. Un istmo es una arista que, si se elimina, divide el grafo en dos componentes conexos. Un árbol es un grafo conexo, por lo que no tiene aristas que puedan eliminarse sin dividir el grafo en dos componentes conexos. Por lo tanto, un árbol no tiene istmos.

e) Falso. Un puente es una arista que, si se elimina, reduce el número de componentes conexos del grafo en uno. Un árbol es un grafo conexo, por lo que no tiene aristas que puedan eliminarse sin reducir el número de componentes conexos en uno. Por lo tanto, un árbol no tiene puentes.

f) Falso. Un árbol es un grafo conexo, por lo que tiene al menos un vértice de grado 1. Esto se debe a que si un grafo no tiene ningún vértice de grado 1, entonces todos los vértices tendrán un grado mayor que 1. Esto significa que todos los vértices estarán conectados entre sí por dos o más aristas. Esto creará un ciclo en el grafo, lo que contradiría la definición de árbol.

g) Falso. Un grafo conexo es un grafo en el que existe un camino entre cualquier par de vértices. Un árbol es un grafo conexo, pero no todos los grafos conexos son árboles. Por ejemplo, un grafo conexo con un ciclo no es un árbol.

h) Verdadero. Un árbol es un grafo conexo, por lo que es siempre un grafo conexo.

i) Verdadero. Un árbol es un grafo no dirigido, por lo que no tiene lazos. Un lazo es una arista que conecta un vértice con sí mismo. Un árbol no puede tener lazos porque esto crearía un ciclo en el grafo.

j) Verdadero. Un árbol es un grafo no dirigido, por lo que no tiene aristas paralelas. Una arista paralela es una arista que conecta los mismos dos vértices. Un árbol no puede tener aristas paralelas porque esto crearía un punto de corte en el grafo.