Autor Tema: Si un grafo tiene tamaño igual al orden tiene al menos un ciclo

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

23 Septiembre, 2022, 02:39 pm
Leído 86 veces

Hibridblood

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 4
  • País: mx
  • Karma: +0/-0
Buenas tardes, alguien tiene una idea de como demostrar la afirmación del título. Si un grafo tiene tamaño igual al orden tiene al menos un ciclo, al igual si el tamaño es mayor o igual al orden +4 tiene 2 ciclos ajenos por vértices

23 Septiembre, 2022, 03:12 pm
Respuesta #1

Luis Fuentes

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

Buenas tardes, alguien tiene una idea de como demostrar la afirmación del título. Si un grafo tiene tamaño igual al orden tiene al menos un ciclo, al igual si el tamaño es mayor o igual al orden +4 tiene 2 ciclos ajenos por vértices

El primero puedes hacer por inducción sobre el número de aristas. Está claro que no existen grafos simples de una o dos aristas con respectivamente uno o dos vértices.

Por otro lado igualmente está claro que un grafo con tres vértices y tres aristas tiene que tener un ciclo: es un triángulo.

Ahora, dado un grafo tiene \( n>3 \) aristas y vértices:

- Si no tiene un vértice de grado \( 1 \), podríamos construir un ciclo tomando aristas consecutivas hasta repetir algún vértice. Tiene un ciclo.

- Si tiene un vértice de grado \( 1 \), si retiramos el vértice y la correspondiente arista, volvemos a tener un grafo de \( n-1 \) aristas y vértices. Por hipótesis de inducción tiene un ciclo y por tanto el grafo original también.

Saludos.

P.D. Para la otra pregunta abre otro hilo. Recuerda que es bueno que indiques que has intentado y que dudas concretas tienes. También que es deseable, sobre todo si se va a preguntar varias veces, mostrar algún tipo de reacción ante las respuesta obtenidas: si las has entendido, si tienes alguna duda, algo...

23 Septiembre, 2022, 04:36 pm
Respuesta #2

Hibridblood

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 4
  • País: mx
  • Karma: +0/-0