¿Existe un gráfico con un solo vértice impar?

Question

Esta pregunta estaba en las diapositivas de mi clase de Matemáticas Discretas y me dijeron que dibujara una. No creo que sea posible. ¿Alguna idea?

Answer 1

Utiliza el Lema del Manipulador para deducir que cualquier grafo tendrá un número par de vértices de grado impar: ya que $$ \displaystyle \sum_{v \in V} \deg v = 2|E| $$ entonces tenemos que la suma de todos los grados de los vértices es PAR. Supongamos que un grafo tuviera un número impar de vértices de grado impar, entonces tendríamos una contradicción ya que obtendríamos $\sum_{v \in V} \deg v =$ algún número de impar. En particular, $1$ es impar, por lo que NO hay ningún gráfico con exactamente un vértice impar.

Answer 2

No. Las palabras mágicas son "Lemma del apretón de manos"