28 votos

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

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.

0 votos

29 votos

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.

6 votos

@Mike: ¡es una respuesta, no un comentario!

38voto

MJD Puntos 37705

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.

15voto

Picaso Puntos 50

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.

0 votos

Esta es una buena respuesta, pero fíjate que la pregunta pedía la suma de los vértices de grado impar, específicamente. ¿Puede ajustar su respuesta para eso?

0 votos

@TheCount:¡Espero que esto funcione ahora!

0 votos

A mí me parece bien. ¡Para su información, yo no era el downvoter, y ahora soy un upvoter!

3voto

AlexR Puntos 20704

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.

1voto

Shabaz Puntos 403

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

1voto

Omar Nagib Puntos 268

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.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X