6 votos

Grafos planares y árboles de expansión

¿Existe un grafo plano cuyas aristas puedan ser coloreadas en rojo, verde o azul de manera que las aristas rojas formen un árbol de expansión, las verdes un árbol de expansión y las azules un árbol de expansión?

Sé que un árbol de expansión debe tocar todos los nodos y esto no se aplica para un gráfico con 3 vértices, pero no estoy muy seguro de cómo ir a demostrar que no existe.

7voto

Tyler Puntos 1

Cada triangulación se descompone en 3 árboles de extensión disjuntos de aristas, cuando se duplican las aristas de una cara triangular. Véase ici .

Sin embargo, si no se duplican las aristas dicha coloración es imposible, ya que un grafo plano tiene como máximo $3n-6$ aristas (fórmula de Euler) y tres árboles de extensión disjuntos, necesitan $3(n-1)$ bordes.

3voto

VHB-Iran Puntos 41

La respuesta es no, excepto para el gráfico con un solo vértice.

Dejemos que $G$ sea un grafo plano conectado con $v$ vértices y $e_1,e_2$ y $e_3$ bordes rojo, verde y azul respectivamente. Suponiendo que las aristas rojas, verdes y azules forman un árbol de spannig, tenemos $v - e_1 = v - e_2 = v - e_3 = 1,$ así $e = 3v - 3$ donde $e = e_1 + e_2 + e_3$ es el número de todas las aristas de $G$ . Para $v \geq 3$ esto contradice $e \leq 3v - 6$ que debe cumplir todo grafo plano conectado con al menos tres vértices. El resto de los casos se comprueban fácilmente.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X