[Julio_fmat]

Demuestre que todo grafo con diametro \( d \) tiene un conjunto independiente de tamaño al menos \( \Big\lceil \dfrac{d+1}{2}\Big\rceil . \)

[Luis Fuentes]

Hola

Demuestre que todo grafo con diametro \( d \) tiene un conjunto independiente de tamaño al menos \( \Big\lceil \dfrac{d+1}{2}\Big\rceil . \)

Si tiene diámetro \( d \), existe un camino de longitud \( d \) entre dos vértices que NO pueden ser conectados por un camino más corto:

\( v_1\to v_2\to v_3\to \ldots\to v_{d+1} \)

En ese subconjunto de vértices las únicas aristas son las de ese camino, ya que en otro caso el camino entre \( v_1 \) y \( v_n \) podría acortarse. Ahora aplica esto:

http://rinconmatematico.com/foros/index.php?topic=111045.msg439081;topicseen#msg439081

Saludos.