Autor Tema: Duda sobre demostración de grafo

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

27 Octubre, 2023, 04:43 pm
Leído 2468 veces

sage

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 18
  • País: es
  • Karma: +0/-0
Hola a todos , tengo dudas de cómo resolver el siguiente ejercicio , si alguién me lo podría explicar  :

1.Demostrar que , si G es un grafo con solo dos vértices de grado impar , entonces ambos vértices han de estar en la misma componente conexa.


Muchas gracias :)

27 Octubre, 2023, 04:59 pm
Respuesta #1

Luis Fuentes

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

Hola a todos , tengo dudas de cómo resolver el siguiente ejercicio , si alguién me lo podría explicar  :

1.Demostrar que , si G es un grafo con solo dos vértices de grado impar , entonces ambos vértices han de estar en la misma componente conexa.

Para cada componente conexa se cumple que si \( V \) el conjunto de vértices:

\( \displaystyle\sum_{v\in v}grado(v)=2\text{nº de aristas} \)

ya que cada arista es incidente en dos vértices. Por tanto la suma de los grados de cada componente conexa ha de ser par.

Saludos.