La idea de una "máxima" gráfico se introdujo en una prueba de Mineral de la Condición. Yo no acababa de llegar a la idea, y me gustaría explicaciones más detalladas.
El teorema y la prueba son como sigue.
Supongamos que G es un grafo con vértices v ($v \ge 3$), y para cada par de vértices no adyacentes $x$ y $y$, $\deg(x)+\deg(y) \ge v$ entonces G es hamiltoniano.
Prueba: Supongamos que el teorema no es cierto. Podemos asumir que todos los aires de vértices no adyacentes satisfacer dado el grado de afección, y que si p y q son los vértices no adyacentes, a continuación, el gráfico formado por la adición de borde de $pq$, denotado $G+pq$, será de hamilton (si no, entonces únete a $pq$ y el uso de la nueva gráfica en lugar de $G$). Podríamos decir que G es máxima para la condición.
Fuente: "Introducción a la Combinatoria" P. 167
A partir de la "Supongamos que el teorema no es cierto", espero que la prueba para decir que la desigualdad se cumple en $G$ pero $G$ no es hamiltoniano. Cómo se relaciona esto con $G+pq$ hamiltoniano? También, hace la sentencia dentro de los paréntesis significa que debo seguir uniendo los vértices no adyacentes hasta obtener una gráfica que es hamiltoniano? Si este es el caso, ¿cómo puedo estar segura de que puedo obtener un hamiltoniano gráfica de este proceso?
