Advertencia: no has iniciado sesión. Tu dirección IP se hará pública si haces cualquier edición. Si
inicias sesión o
creas una cuenta, tus ediciones se atribuirán a tu nombre de usuario, además de otros beneficios.
Puedes deshacer la edición.
Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual |
Tu texto |
Línea 106: |
Línea 106: |
| X(G) = X(Gc) = 1 -> 2 <= 2 OK | | X(G) = X(Gc) = 1 -> 2 <= 2 OK |
| * PI: | | * PI: |
| <br> Sea G un grafo de n vértices, q.v.q. X(G) + X(Gc) <= n+1
| | Saco un vertice -> G' = G-v |
| <br>HI: Sea G' un grafo con n' vértices con n'<n entonces X(G') + X(G'c) <= n'+1
| | <br>X(G)+X(Gc) = X(G')+X(Gc')+k (k cte.). Separamos en casos: |
| <br>Saco un vertice a G -> G' = G-v
| | <br>1. X(G) = X(G') o X(Gc) = X(Gc') -> k <= 1 -> X(G)+X(Gc) <= X(G')+X(Gc')+1 <= (HI) n+1 OK |
| <br>X(G)+X(Gc) = X(G')+X(G'c)+k (k cte.). Separamos en casos: | | <br>2. dG(v) >= X(G') y dGc(v) >= X(Gc') -> |
| <br>Caso 1. X(G) = X(G') o X(Gc) = X(G'c) -> k <= 1 (ya que a lo sumo se puede reducir en 1 color al quitar un vértice) | | X(G') <= X(G) + 1 <= dG(v) + 1 y |
| <br> -> X(G)+X(Gc) = X(G')+X(G'c)+k <= X(G')+X(G'c) + 1 <=(HI) n'+2 = (n-1)+2 = n+1 OK
| | X(G'c) <= X(Gc) + 1 <= dGc(v) + 1 entonces |
| <br>Caso 2. X(G) > X(G') y X(Gc) > X(G'c) | | <br>X(G') + X(G'c) <= dG(v) + dGc(v) + 2 (como dGc(v)=n-dG(v)-1) dG(v)+(n-dG(v)-1)+2 = n+1 OK |
| <br> -> dG(v) >= X(G') y dGc(v) >= X(G'c) (ya que v agrega un color a ambos grafos por lo que en ambos es adyacente a cada color al menos una vez)
| |
| <br> -> X(G) = X(G')+1 y X(Gc) = X(G'c)+1 (porque agregar un vértice no puede agregar más de un color)
| |
| <br> -> X(G) + X(Gc) = X(G') + X(G'c) + 2 <= dG(v) + dGc(v) + 2 = n-1 + 2 = n+1 OK | |
|
| |
|
| <br>b) Probamos ambas desigualdades: | | <br>b) Probamos ambas desigualdades: |