Autor Tema: Grafo planar menos de 12 vértices, existe v con \(\deg(v)\le 4\)

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

22 Noviembre, 2019, 05:08 am
Leído 3523 veces

Julio_fmat

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,927
  • País: cl
  • Karma: +0/-2
  • Sexo: Masculino
    • Fmat
Demuestre que todo grafo planar con menos de \( 12 \) vértices tiene un vértice con grado menor o igual que \( 4. \)
"Haz de las Matemáticas tu pasión".

22 Noviembre, 2019, 08:27 am
Respuesta #1

Luis Fuentes

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

 Intenta poner títulos algo más descriptivos (como los que he puesto yo tras modificar tus mensajes) y no simplemente: "Grafo planar 1", "Grafo planar 2", "Grafo planar 3", etcétera...

Demuestre que todo grafo planar con menos de \( 12 \) vertices tiene un vertice con grado menor o igual a \( 4. \)

 Un grafo planar cumple:

\(   m\leq 3n-6 \)

 siendo \( m \) el número de aristas y \( n \) el de vértices.

 Si no existiese un vértice con grado menor o igual que \( 4 \), todos los vértices tendrían grado mayor o igual que \( 5 \). Por tanto:

\(  3n-6\geq m=\dfrac{1}{2}\displaystyle\sum_{v\in V} deg(v)\geq \dfrac{5n}{2} \)

 De donde \( n\geq 12 \).

Saludos.