Teoría de Grafos: Verdadero o Falso

Question

Un par de problemas de Verdadero/Falso en los que estoy trabajando. No se requiere una prueba completa, sólo si las afirmaciones son válidas o no.

1) Si $G$ contiene un paseo cerrado, entonces $G$ contiene un ciclo.

Falso

2) Que $G$ sea un grafo conexo. Si $G$ no tiene puentes, entonces $G$ no tiene vértices cortados.

Falso. Un contraejemplo es bastante fácil de generar; dos triángulos con un vértice común darán lugar a un grafo con 5 vértices y 6 aristas que contiene 1 vértice cortado y ningún puente.

3) Supongamos $G$ y $H$ son grafos isomorfos. Si $G$ es un árbol, entonces $H$ es un árbol.

Verdadero

4) Supongamos $G$ y $H$ son grafos isomorfos. Si $G$ está conectado, entonces $H$ está conectado.

Verdadero

5) Si cada componente conexa de $G$ es bipartita, entonces $G$ es bipartita.

Verdadero

6) Si $G$ es un árbol regular, el $G$ es $K_1$ o $K_2$ .

Cierto.

Answer 1

(1) es falsa. Un ciclo es un paseo cerrado sin vértices repetidos excepto por terminar en el vértice donde empezó. La dirección $2$ -punto ruta $P_2$ tiene un paseo cerrado (caminar de un extremo a otro y viceversa) pero sin bicicletas.

(5) es verdadera. (Puede ser útil recordar que un grafo es bipartito si y sólo si es $2$ -colorable. En términos más generales, un grafo es $n$ -si y sólo si cada componente conexo es $n$ -colorable).

El resto de tus respuestas son correctas. El hecho de que no seguro sobre las respuestas a (3) y (4) es un poco preocupante. ¿Quizá no tienes muy claro el concepto de isomorfismo?

Answer 2

(1) es falsa por contraejemplo de bof. (2) es como tú dices.

Respecto a los grafos isomorfos (3) y (4)

Debe saber que el término isomorfo significa literalmente que son el mismo gráfico. Todo lo que tienes que hacer es mover los vértices y obtendrás el mismo gráfico. Así que, por supuesto, si $G$ y $H$ son isomorfos, entonces ambos son árboles o no, y ambos están conectados o no, porque son el mismo grafo.

Respecto a los grafos bipartitos (5)

Sea $C_1, C_2, C_3, \ldots$ sean las componentes conexas de un grafo $G$ y supongamos que son bipartitas con conjuntos de vértices $C_1 = A_1 \cup B_1, C_2 = A_2 \cup B_2, C_3 = A_3 \cup B_3, \ldots$ es decir $A_i$ son la primera parte y $B_i$ son la segunda parte de cada componente conectada. Entonces deberías poder demostrar que $A_1 \cup A_2 \cup \cdots$ y $B_1 \cup B_2 \cup \cdots$ forman dos conjuntos disjuntos de vértices cuya unión es $G$ y que esto hace que $G$ bipartito (no hay dos vértices en $A_1 \cup A_2 \cup \cdots$ están conectadas por una arista, y lo mismo para $B_1 \cup B_2 \cup \cdots$ ).

En cuanto a los árboles regulares (6)

Esto es cierto porque todo árbol tiene hojas . Así que tienes razón.