Análisis combinatorio, teoría de gráficas ¿Como resolver el siguiente ejercicio: Encuentra todas las posibles gráficas...
- Encuentra todas las posibles gráficas regulares que al mismo tiempo son árboles. Después, demuestre porque no es posible encontrar más gráficas con estas dos propiedades. Las propiedades son: planaridad y coloración
1 Respuesta
Respuesta de Valero Angel Serrano Mercadal
1
·
·
¡Hola Caolinaboni!
Teorema 4, pág. 16. Todo árbol con al menos una arista tiene algún vértice terminal.
Luego si es un árbol con aristas:
Para ser regular tendrá que tener todos los vértices de orden 1. La suma de los órdenes de los vértices será p.
Las aristas de un árbol son p-1, luego la suma de los ordenes de los vértices es 2(p-1)
Luego deberá cumplirse
p=2(p-1)
p=2p - 2
p=2
Y será un árbol de dos vértices con la arista que los une.
Y si es un árbol sin aristas, como hay un camino entre cualesquiera dos puntos, solo podrá haber un vértice.
·
Resumiendo: El árbol con un solo vértice y el árbol con dos vértices y una arista.
La otra pregunta no la entiendo.
