Autor Tema: Grado máximo de un grafo G

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

18 Noviembre, 2019, 05:20 am
Leído 856 veces

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Sea \( G \) un grafo tal que \( m(G)>n(G) \). Demuestre que el grado maximo de \( G \) es mayor o igual a \( 3. \)

Hola, multiplicando por 2 en la desigualdad, obtenemos una cota para la suma de los grados de los vertices. Es decir, como \( m>n \), entonces \( 2m>2n. \) Luego, \( \displaystyle\sum_{v\in V} \deg(v)>2n. \)
"Haz de las Matemáticas tu pasión".

18 Noviembre, 2019, 08:30 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,123
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Sea \( G \) un grafo tal que \( m(G)>n(G) \). Demuestre que el grado maximo de \( G \) es mayor o igual a \( 3. \)

Hola, multiplicando por 2 en la desigualdad, obtenemos una cota para la suma de los grados de los vertices. Es decir, como \( m>n \), entonces \( 2m>2n. \) Luego, \( \displaystyle\sum_{v\in V} \deg(v)>2n. \)

Razona por reducción al absurdo. Si el grado máximo no es mayor o igual que \( 3 \), quiere decir que todos los vértices tienen grado menor o igual que dos. Entonces:

\( 2m=\displaystyle\sum_{v\in V} \deg(v)\leq \displaystyle\sum_{v\in V} \deg(v)2=2n \)

Lo cuál contradice que \( m>n \).

Saludos.