[MikeHEndrix]

Hola buenos días, llevo unos días liado haciendo ejercicios para aprobar un examen de la universidad, si le entrego todos los ejercicios apruebo. El caso es que hay varios que no llego a asaber hacer, no se me ocurre la idea feliz. Estos son:

1. Dado un grafo G (sin lazos ni lados paralelos) se define el complementario de G, G, como el grafo cuyo conjunto de vértices es el mismo que de G, y para el que existe un lado que une los vértices u y v si, y sólo sí, en G no existe un lado que una esos dos vértices. Demuestra que si G es no conexo, el complementario de G es conexo. Es cierto que si G es conexo
su complementario no lo es?

2. Un grafo G se dice autocomplementario, si G =~ G.
a. Demuestra que si G es autocomplementario y tiene n vértices, entonces el número de lados es (n(n−1)) / 4.
b. Demuestra que si G es autocomplementario, entonces G tiene 4k ó 4k + 1 vértices.
c. Encuentra todos los grafos autocomplementarios de 4 y de 5 vértices.
d. Encuentra un grafo autocomplementario de 8 vértices.
e. Encuentra todos los árboles que sean autocomplementarios

3. Demuestra que si un grafo G tiene 11 vértices o más, entonces, o bien G, o bien G no esplano. G es el grafo complementario

4. Demuestra que si colocamos las 28 fichas del dominó en fila, de forma que si una ficha está junto a otra los cuadrados adyacentes son del mismo valor, entonces los valores de los cuadrados inicial y final son el mismo.
Si tuviéramos un dominó con 36 fichas, en la que los valores marcados en cada una fueran de 0 a 7, sería posible colocarlas todas en fila como hemos explicado en el apartado anterior?

5. Demuestra que si un grafo tiene a lo sumo cinco vértices y uno de ellos es de grado dos entonces es plano.

6. Un árbol tiene 33 vértices de grado uno, 25 vértices de grado 2, 15 vértices de grado 3, y el resto, vértices de grado 4. Calcula cuántos vértices tiene en total.

7. Demuestra que en todo grafo (sin lazos ni lados paralelos) con más de un vértice existen dos vértices con el mismo grado.


Muchas gracias!

[Luis Fuentes]

Hola

1. Dado un grafo G (sin lazos ni lados paralelos) se define el complementario de G, G, como el grafo cuyo conjunto de vértices es el mismo que de G, y para el que existe un lado que une los vértices u y v si, y sólo sí, en G no existe un lado que una esos dos vértices. Demuestra que si G es no conexo, el complementario de G es conexo. Es cierto que si G es conexo
su complementario no lo es?

Si \( G \) no es conexo sea \( G_1 \) una componente conexa de \( G \) y \( G=G_1\cup G_2 \). Entonces sea \( v_1\in G_1 \) y \( v_2\in G_2 \) vértices. Por estar en distintas componentes conexas la arista \( (v_1,v_2) \) está en \( \underline{G}. \) Ahora dado cualquier otro vértice \( v \), si está en \( G_i \) entonces la arista \( (v,v_{3-i}) \) está en \( \underline{G}. \)

Para ver que puede ocurrir si \( G \) es conexo, piensa en un pengágono.

2. Un grafo G se dice autocomplementario, si G =~ G.
a. Demuestra que si G es autocomplementario y tiene n vértices, entonces el número de lados es (n(n−1)) / 4.

Utiliza que la suma del número de aristas de un grafo y su complementario es el número de aristas del grafo completo de n vértices. Si el grafo es autocomplementario tiene el mismo número de aristas que su complementario.

b. Demuestra que si G es autocomplementario, entonces G tiene 4k ó 4k + 1 vértices.

Utiliza el apartado anterior: \( n(n-1)/4 \) debe de ser un número entero.

c. Encuentra todos los grafos autocomplementarios de 4 y de 5 vértices.

Papel y bolígrafo (¡o lápiz!). Por el apartado (a) sabes cuantas aristas pueden tener.

d. Encuentra un grafo autocomplementario de 8 vértices.

Inténtalo.

e. Encuentra todos los árboles que sean autocomplementarios[/i]

Utiliza que un árbol de \( n \) vértices tiene \( n-1 \) aristas y el apartado (a).

3. Demuestra que si un grafo G tiene 11 vértices o más, entonces, o bien G, o bien G no esplano. G es el grafo complementario

Utiliza que un grafo plano a lo sumo tiene \( 3n-6 \) aristas.

4. Demuestra que si colocamos las 28 fichas del dominó en fila, de forma que si una ficha está junto a otra los cuadrados adyacentes son del mismo valor, entonces los valores de los cuadrados inicial y final son el mismo.
Si tuviéramos un dominó con 36 fichas, en la que los valores marcados en cada una fueran de 0 a 7, sería posible colocarlas todas en fila como hemos explicado en el apartado anterior?

Ten en cuenta que en un dominó usual hay siete fichas con cada número, pero en una de ellas aparece doble. Es decir hay un número par de semi-fichas con cada número.

5. Demuestra que si un grafo tiene a lo sumo cinco vértices y uno de ellos es de grado dos entonces es plano.

Todo grafo con cuatro o menos vértices es plano. Dibuja uno con cinco vértices con el mayor número posibles de aristas en las condiciones del enunciado.

6. Un árbol tiene 33 vértices de grado uno, 25 vértices de grado 2, 15 vértices de grado 3, y el resto, vértices de grado 4. Calcula cuántos vértices tiene en total.

Utiliza que la suma de los grados de un grafo es el doble del número de aristas y que un árbol tiene una arista menos que el número de vértices.

7. Demuestra que en todo grafo (sin lazos ni lados paralelos) con más de un vértice existen dos vértices con el mismo grado.

Teniendo en cuenta que el grado de un grafo de \( n \) vértices como mínimo es cero y a lo sumo es \( n-1 \), un grafo con todos los vértices de distinto grado necesariamente tendría un vértice de grado cero y otro de grado \( n-1 \). ¿Es eso posible?.

Saludos.