¿Es todo bosque con más de un nodo un grafo bipartito?

Question

Esta es una pregunta de mi examen de hoy:

La definición de un grafo bipartito es "Un grafo con al menos dos nodos es bipartito si y sólo si no hay ningún ciclo de longitud impar en el grafo".

Recordaremos que en un bosque, y en un árbol en particular, no hay ciclos en absoluto.

¿Cuál de las siguientes afirmaciones es cierta?

1) Todo bosque con más de un nodo es un grafo bipartito.

2) La afirmación anterior es falsa, pero todo árbol con más de un nodo es un grafo bipartito.

3) Un árbol con un número impar de nodos es nunca un gráfico bipartito.

4) Ninguna de las afirmaciones anteriores es cierta.

Elegí el 1, más por razones lógicas que por razones de teoría de grafos.. Un grafo bipartito se definió como un grafo sin ciclo de longitud impar en el grafo; un bosque se definió como un grafo sin ciclos - ergo un bosque es un grafo bipartito. (Todo esto bajo el supuesto de que el bosque tiene dos o más nodos)

Actualmente hay una discusión sobre si la respuesta es 1 o 4 - el argumento detrás de 4 es que un bosque puede tener nodos no conectados; yo no veo esto como una contradicción a la posibilidad de que el bosque sea un gráfico bipartito, pero otras personas sí.

Agradecería alguna aclaración al respecto :). Gracias de antemano.

Answer 1

Lo que necesitas es la siguiente observación/resultado:

Propuesta : Un grafo es bipartito si y sólo si el conjunto de vértices/nodos puede dividirse en dos subconjuntos de tal manera que en un subconjunto dado, no hay dos vértices conectados.

Piénsalo un poco y te quedará claro. Pero entonces, ves que un gráfico sin ciclos es claramente bipartito. Porque si tienes un árbol, elige una raíz. Entonces pones esta raíz en un conjunto; pones sus vecinos en el segundo conjunto; pones los vecinos de los vecinos en el primer conjunto, etc. Como no hay ningún ciclo, para cualquier elección de dos vértices en un subconjunto dado, no serán adyacentes. Ahora, si tienes un bosque, divide cada árbol por separado.

---

Esta es la forma en que yo demostraría que un bosque es bipartito, pero esto es sólo porque estoy más familiarizado con la definición que implica una partición del conjunto de vértices. Por otro lado, por razones vacuas, un bosque es bipartito, exactamente porque no tiene ningún ciclo impar (ya que no tiene cualquier ciclo). Sin embargo, a veces ocurre que nos resistimos a creer que algo es cierto por razones vacías. Por eso escribí la solución anterior.

Answer 2

Un gráfico es bipartito si y sólo si , no tiene un ciclo - de longitud impar.

• Si su gráfico es un bosque, cada componente conectado es un árbol y cada árbol, por definición, es un gráfico acíclico conectado $\rightarrow$ por lo que, al no tener ciclos, seguramente tampoco tiene ciclos de longitud impar, por lo que todo componente conectado es bipartito $\rightarrow$ un bosque es bipartito.
• si su gráfico es un árbol (un gráfico conectado, acíclico) por definición también es bipartito

Por lo tanto, creo que tanto 1) como 2) son correctos