Demostrar que el número de vértices de grado impar en cualquier grafo G es par

Question

Tengo un pequeño problema con la siguiente pregunta

Dado $G$ es un grafo no dirigido, el grado de un vértice $v$ , denotado por $\mathrm{deg}(v)$ , en el gráfico $G$ es el número de vecinos de $v$ .
Demostrar que el número de vértices de grado impar en cualquier gráfico $G$ está en paz.

Answer 1

Pongo el comentario de Mike como respuesta, ya que él no lo hará.

La suma de todos los grados es igual al doble del número de aristas. Como la suma de los grados es par y la suma de los grados de los vértices con grado par es par, la suma de los grados de los vértices con grado impar debe ser par. Si la suma de los grados de los vértices con grado impar es par, debe haber un número par de esos vértices.

Answer 2

Sea G un gráfico con $'e'$ bordes y $'n'$ vértices $v_1,v_2,v_3,...,v_n$ . Como cada arista es incidente en dos vértices, contribuye $2$ a la suma de grados de los vértices del gráfico $G$ . Así, la suma de grados de todos los vértices en $G$ es el doble del número de aristas en $G$ . Por lo tanto, $$\sum_{i=1}^n\text{degree}(v_i)= 2e.$$ Que los grados de la primera $r$ vértices sean pares y los restantes $(n-r)$ Los vértices tienen grados Impares, entonces claramente, $\sum_{i=1}^{r}\text{degree}(v_i)= even $ .desde, $$\sum_{i=1}^n\text{degree}(v_i)= \sum_{i=1}^r\text{degree}(v_i)+\sum_{i=r+1}^n\text{degree}(v_i)$$ $\implies$ $\sum_{i=1}^n\text{degree}(v_i)- \sum_{i=1}^r\text{degree}(v_i)=\sum_{i=r+1}^n\text{degree}(v_i)$

$\implies$ $\sum_{i=r+1}^n\text{degree}(v_i)$ es par.( $WHY?$ )

Pero, el for $i=r+1,r+2,...,n$ cada $d(v_i)$ es impar. Así, el número de términos en $\sum_{i=r+1}^n\text{degree}(v_i)$ debe ser uniforme.

En palabras lúcidas, $(n-r)$ está en paz.

De ahí el resultado.

Answer 3

Representamos $G$ por una relación simétrica sobre el conjunto de puntos $P$ que también llamamos $G$ Así que $$G = \{(a,b), (b,a) : \text{there is an edge between } a \text{ and } b\}$$ Claramente, $\#G |2$ donde $\#G$ es el número de elementos en $G$ . Ahora $$\deg (a) = \# \{(a,x): (a,x) \in G\}$$ Ya que tenemos $$\sum_{a\in P} \deg(a) = \sum_{a\in P} \# \{(a,x): (a,x) \in G\} = \#\{(x,y) : (x,y) \in G\} = \# G$$ Sabemos que $$\sum_{a\in P} \deg (a) | 2$$ De la teoría de los números tenemos $$\sum_{j=1}^n a_j |2 \Leftrightarrow \#\{a_j : a_j \not|\, 2\}|2$$ (el número de números Impares en una suma es par, si la suma es par) y estableciendo $a_j = \deg(b_j)$ con $b_j \in P$ una enumeración de $P$ La afirmación es la siguiente.

Answer 4

Supongamos que tenemos un gráfico arbitrario con $l$ vértices. Supongamos que tenemos $n$ vértices con grado impar. Consideremos qué ocurre cuando conectamos (o eliminamos) una arista entre dos vértices cualesquiera, hay dos posibilidades:

1) Los dos vértices son ambos de grado par(o impar): Supongamos que ambos vértices son de grado par. Conectando(o eliminando) una arista entre ellos se incrementará el grado de ambos vértices en $1$ (o disminuye en caso de eliminar una arista), por lo que ambos vértices pasarán a ser de grado impar, y $n$ aumentará en $2$ .

Del mismo modo, si los dos vértices eran inicialmente de grado impar, entonces la conexión (o eliminación) de una arista convertirá ambos vértices en grado par, y $n$ disminuirá en $2$ .

2) Un vértice es impar mientras que el otro es par. En este caso, al conectar (o eliminar) una arista, el vértice impar se convierte en par, y el vértice impar pasa a ser par. Por lo tanto, $n$ se mantendrá sin cambios.

De esto aprendemos que el número de vértices de grado impar $n$ sólo puede aumentar/disminuir en pasos de $2$ (o permanecen sin cambios) a medida que creamos(eliminamos) aristas.

Ahora, cuando construyamos cualquier gráfico que deseemos, empezaremos con nuestros vértices aislados unos de otros, sin una sola conexión (arista). Por lo tanto, inicialmente $n=0$ (todos los vértices son de grado par ya que no hay ninguna arista que los conecte) , y a medida que hacemos conexiones, sólo puede aumentar/disminuir en pasos de $2$ Por lo tanto $n$ se mantendrá uniforme.

Answer 5

Pista: ¿Cuál es la suma de los grados de todos los vértices?