Teoría de Grafos: Gráfico simple

Question

Demuestre que, si $G$ es simple, el gráfico de aristas de $G$ tiene $E(G)$ vértices y $\sum {d(v) \choose 2}$ bordes.

Sé que un gráfico de aristas de un gráfico $G$ es el gráfico con el conjunto de vértices $E(G)$ en el que $2$ los vértices se unen si y sólo si son aristas adyacentes en $G$ . Así que, lógicamente, parece bastante claro que si $G$ es simple, el gráfico de aristas tiene $E(G)$ vértices. Sin embargo, acabo de empezar este curso, así que todavía no estoy muy familiarizado con la forma de demostrar las cosas. Además, no tengo ni idea de cómo demostrar la segunda parte de esto. Cualquier ayuda sería genial, gracias.

Answer 1

Sugerencia: para ser específicos, imagine un vértice en $G$ de grado $4$ . Cada par de aristas (en $G$ ) incidente en el vértice dará una arista en $E(G)$ . ¿Cuántas parejas de este tipo hay?

Answer 2

Para demostrar esta afirmación basta con contar las aristas del gráfico de aristas.

Existe una arista en el gráfico de aristas si hay dos aristas adyacentes en el gráfico original. Las dos aristas tendrían que compartir un vértice. En lugar de mirar las aristas, vamos a mirar los vértices.

Para un vértice, $d(v)$ es el número de aristas que inciden en ese vértice. Dos aristas que inciden en el mismo vértice son aristas adyacentes. Por lo tanto, hay $\binom{d(v)}{2}$ aristas adyacentes por vértice. Así, el vértice $v$ representa esa cantidad de aristas en el gráfico de aristas.

Como el gráfico es simple, dos aristas no serán adyacentes en más de un vértice. De lo contrario, se trataría de una arista doble. Por lo tanto, cada arista en el gráfico de aristas sólo se cuenta una vez con nuestro método.

Así que hay $\sum_{v} \binom{d(v)}{2}$ aristas en el gráfico de aristas.

Answer 3

Entienda esto de una manera muy simple. Si tienes algo, digamos simplemente una línea, entonces esa línea tendría dos vértices, cada uno de ellos con grado 1, y una sola arista, por lo que si sumas los grados de todos los vértices, eso se convierte en 2, que es el doble del número de aristas. Por lo tanto, el número de aristas es igual a la suma de los grados de todos los vértices dividida por 2. Ahora bien, hay que tener una idea general de que en un gráfico el grado de un vértice es el número de aristas adyacentes a él y cada arista contribuye con 1 al grado del vértice al que está unido. Por lo tanto, cualquier arista contribuirá en realidad a un grado total de 2 por estar unida a dos vértices. Así, ahora puedes entender cómo el número total de aristas es igual a la mitad de la suma de los grados de todos los vértices.