Autor Tema: Grafo plano conexo con A=16 y grados>=4. ¿Vértices?

0 Usuarios y 1 Visitante están viendo este tema.

13 Enero, 2023, 11:45 am
Leído 2832 veces

Maribrevas

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 35
  • Karma: +0/-1
  • Sexo: Femenino
Me podrían ayudar, por favor. Sea G un grafo conexo con 16 aristas, todos sus vértices tienen Valencia igual o superior a 4 y plano. ¿Cuántos vértices tiene? Estoy perdida.

13 Enero, 2023, 12:06 pm
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

Me podrían ayudar, por favor. Sea G un grafo conexo con 16 aristas, todos sus vértices tienen Valencia igual o superior a 4 y plano. ¿Cuántos vértices tiene? Estoy perdida.

Recuerda que la suma de la valencias de todos los vértices es el doble del número de aristas. Por tanto como cada vértice tiene valencia \( \geq 4 \), si hay \( n \) vértices:

\( 4\cdot n\leq 2\cdot 16 \)

Es decir \( n\leq 8 \). (i)

Por otra parte todo grafo conexo plano con \( a \) aristas y \( n\leq 3 \) vértices cumple que \( a\leq 3n-6 \), por tanto:

\( 16\leq 3n-6 \) es decir \( n\geq 22/3 \) (ii)

De (i) y (ii) \( n=8 \).

Saludos.