Duda con la prueba de si$G$ es simple y$\delta\geq\frac{n-1}2$, entonces$G$ está conectado

Question

La proposición. Si $G$ es simple y $\delta\geq\frac{n-1}2$,, a continuación, $G$ está conectado.

Prueba. Asumir lo contrario. A continuación, $G$ tiene al menos dos componentes, dicen $G_1$, $G_2$. Deje $v$ ser cualquier vértice de $G_1$. Como $\delta\geq\frac{n-1}2$, $d(v)\geq\frac{n-1}2$. Todos los vértices adyacentes a $v$ en $G$ debe pertenecer a $G_1$. Por lo tanto, $G_1$ contiene al menos $d(v)+1\geq\frac{n-1}2+1=\frac{n+1}2$ vértices.

Del mismo modo, $G_2$ contiene al menos $\frac{n+1}2$ vértices. Por lo tanto, $G$ tiene al menos $\frac{n+1}2+\frac{n+1}2=n+1$ vértices, lo cual es una contradicción. $\square$

En el método de contradicción, podemos utilizar la hipótesis? Por lo general, nos demuestran supongamos $G$ no está conectada $\implies$ tiene al menos dos componentes conectados $\implies$ alguna consecuencia $1$ $\implies$ alguna consecuencia $2$...$\implies$ ... alguna consecuencia $n$, lo que contradice la hipótesis. Pero aquí se utiliza la hipótesis de $\delta\ge (n-1)/2$ para la prueba.

Puede usted explicar por qué lo hicieron uso de este tipo?

Answer 1

Sí, usted puede utilizar la hipótesis de que en una prueba por contradicción. Esta es una de las señas de identidad de un "verdadero" de la prueba por contradicción, en vez de una prueba por contraposición.

En general, para demostrar $P \to Q$ por la contradicción, usted asume tanto $P$ y la negación de la $Q$ y tratar de obtener alguna contradicción. Esto es a veces más fácil que trabajar por contraposición, donde sólo suponga la negación de la $Q$ e intentará demostrar que la negación de la $P$. Puede ser más fácil porque usted tiene más hipótesis para trabajar con.

En general, si $P$ y la negación de la $Q$ son incompatibles, siempre que $P$ mantiene vemos a $Q$ tiene que llevar a cabo, lo que significa que $P$ implica $Q$.

Answer 2

La prueba se ve como circulus vitiosus. Pero parece que $n$ indica el número de vértices, y la suposición conduce a $n+1$, lo cual es una contradicción,

desde un finito gráfico sólo puede tener un número finito de vértices que es un número natural, y no hay ningún número natural con $n = n+1$.

Así que no veo el problema, ya que la prueba de la siguiente manera esta prueba válida esquema:

 G, ~A |- f
 ----------
   G |- A

Los supuestos G no necesita ser vacío, aquí es la condición de la proposición.