Preguntas sobre teoría de grafos y árboles

Question

(a) Es falso .

Si $G$ es un árbol entonces: $|E|=|V|-1$

Así que, $|E|=9-1=8$ . Pero como la suma de los grados de todos los vértices es igual a $2|E|$ tenemos $2|8|=16\neq18$

(b) Es cierto

Si $G$ es un gráfico entonces: $|E| \geq |V|-|W| $ donde |W| es el número de partes conectadas del grafo. Tenemos $|E| \geq |V|-|W| $ Así que $|7| \geq 12-5=7$

(c) Es falso .

$|E| \geq |V|-|W| $

Así que $24 \geq 30-5=25$ y esto es falso

¿Cómo puedo demostrar que (d),(e) son falsas?

EDITAR :

(d) Es falso

Si el gráfico es acíclico entonces es un bosque y tenemos $|E|=|V|-1$ , por lo que deberíamos tener $9=9-1=8$ que es imposible.

Answer 1

Elige un subgrafo del grafo (e) que sea un árbol. Tiene 4 aristas. Entonces añade las 8 aristas que faltan una a una. Cada vez que añades una arista, conecta vértices que ya están conectados, por lo que se añade al menos un ciclo simple; así que no hay menos de 8 ciclos simples en ese grafo.

Answer 2

He descubierto que si un gráfico $G$ está conectado y $|E|=|V|+k$ entonces $G$ tiene al menos $k+1$ ciclos.

En caso de (e) tenemos $12=5+k \Leftrightarrow k=7$ .

Así que $G$ tiene al menos $8$ ciclos.

Conclusión: (e) es falso porque dice que $G$ tiene menos de $8$ ciclos.