UTNianos

Tengo una consulta con dos ejercicios de grafos de la guía

El 2)d) dice:

Cita:Si G es un grafo conexo con #A=26 y gr(v)>= 4 para todos los vértices de V, se pide indicar el mayor número del cardinal que puede alcanzar V.

Yo hice lo que está en el attachment.
¿Tiene sentido o mandé fruta mal?

El 2) e) dice

Cita:Si G es un grafo simple con 52 aristas, dar el menor número de vértices que puede tener.

¿Se aplica la misma propiedad, aún cuando no sabemos cómo están distribuidos los grados de los vértices, como en otros ejercicios donde dice "hay 3 vértices de grado 5, 4 de grado 6, etc?

Hola,

(01-02-2018 18:17)Apellidocomplicado escribió: [ -> ]

Cita:Si G es un grafo conexo con #A=26 y gr(v)>= 4 para todos los vértices de V, se pide indicar el mayor número del cardinal que puede alcanzar V.

¿Por qué multiplicás los vértices por los grados de los vértices? Además escribís \[V\cdot g(v)=2A\] como ecuación y luego \[V\cdot 4\geq 2A\] como inecuación, pero llegás al resultado correcto.

Si todos los n vértices tienen orden 4, deben haber \[\dfrac {4n}2=2n\] aristas. Como nos dicen que el número de aristas es 26 debe ser \[n\leq 13.\]

---

(01-02-2018 18:17)Apellidocomplicado escribió: [ -> ]

Cita:Si G es un grafo simple con 52 aristas, dar el menor número de vértices que puede tener.

¿Se aplica la misma propiedad, aún cuando no sabemos cómo están distribuidos los grados de los vértices, como en otros ejercicios donde dice "hay 3 vértices de grado 5, 4 de grado 6, etc?

No. Un grafo simple completo de n vértices, tiene como máximo número de aristas \[\dfrac {n(n-1)}2\] con n vértices. Para \[n=10\] son 45 aristas, insuficiente, y para \[n=11\] son 55. Debe tener por tanto al menos 11 vértices.

P.D.: La imagen es innecesaria en este caso, ya que todo lo que aparece se puede teclear. Recordá usar para las fórmulas LaTeX: acá podés ver cómo se utiliza.

Saludos