Autor Tema: Problema de Grafos 2

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

19 Noviembre, 2019, 03:18 pm
Leído 790 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 de tamaño \( \displaystyle{{k}\choose{2}}+1 \) y de grado maximo al menos \( 2 \). Demuestre que existe un conjunto \( U\subset V(G) \) tal que \( \left |{U}\right |=k+1 \) y \( G\left[U\right] \) no tiene vertices aislados.

Hola, como podemos hacer este problema? ???
"Haz de las Matemáticas tu pasión".

19 Noviembre, 2019, 06:12 pm
Respuesta #1

Luis Fuentes

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

Sea \( G \) un grafo de tamaño \( \displaystyle{{k}\choose{2}}+1 \) y de grado maximo al menos \( 2 \). Demuestre que existe un conjunto \( U\subset V(G) \) tal que \( \left |{U}\right |=k+1 \) y \( G\left[U\right] \) no tiene vertices aislados.

Hola, como podemos hacer este problema? ???

Como el grado máximo es dos, tiene al menos un vértice \( v_1 \) de grado dos con dos vecinos \( v_2,v_3 \).

1) Se cumple que dado un conjunto \( U \) cualquiera de \( k+1 \) vértices conteniendo a \( v_1,v_2,v_3 \) con dos o más vértices aislados, puede construrirse otro con el mismo número de vértices \( k+1 \) conteniendo a \( v_1,v_2,v_3 \) y estrictamente menos vértices aislados.

Spoiler
Dado un conjunto \( U \) cualquiera de \( k+1 \) vértices conteniendo a \( v_1,v_2,v_3 \) supón que tiene dos o más vértices aislados dos o más vértices aislados, entonces \( G(U) \) a lo sumo contiene \( \displaystyle\binom{k-1}{2}<\displaystyle{{k}\choose{2}}+1 \) aristas y por tanto existe un arista \( e \) con al menos un vértice fuera de \( U \).

Si tiene un vértice fuera de \( U \) quitamos de este conjunto uno de los vértices aislados y metemos ese vértice, que ya no estará aislado.

Si tiene dos vértices fuera de \( U \) quitamos los dos aislados de ese conjunto y metemos los dos de \( e \), que ya no estarán aislados.
[cerrar]

2) Por tanto existe un conjunto \( U \) de \( k+1 \) vértices conteniendo a \( v_1,v_2,v_3 \) conteniendo al lo sumo un vértice aislado.

To be continued…

Continúo:

Dado un conjunto \( U \) de \( k+1 \) vértices conteniendo a \( v_1,v_2,v_3 \) con exactamente sumo un vértice aislado \( v_a \), a lo sumo tiene \( \displaystyle\binom{k}{2}<\displaystyle{{k}\choose{2}}+1 \) aristas, por tanto hay una arista fuera de \( G(U) \) con uno o dos vértices fuera de \( U \).

Si esa arista sólo tiene un vértice fuera de \( U \), lo sustituimos por el vértice aislado y ya tenemos un conjunto de \( k+1 \) vértice sin aislados.

Si esa arista tiene dos vértices fuera de \( U \), notamos lo siguiente. La componente conexa de G(U) que contiene a \( v_1,v_2,v_3 \) o bien tiene un vértice de grado 1, que retirado sigue dejando a todos los demás sin aislar o bien tiene todos los vértices de grado mayor que 1, con lo cual retirando cualquiera de ellos sigue dejando a los demás sin aislar. Es decir en cualquier caso tenemos un vértice en esa componente conexa que podemos retirar. Intercambiamos ese vértice y el aislado \( v_a \) por los dos vértices de la arista externa y ya tenemos un conjunto sin vértices aislados.

Saludos.