Dada a matriz de incidência de um grafo, dê uma interpretação para a soma dos elementos da
sima linha e a soma dos elementos na
esima coluna. Baseado nestas interpretacões, dê uma nova demonstração para o teorema 8.1.
(Sugestão: expresse o somatório de todos os elementos da matriz de incidência de duas maneiras diferentes, somando primeiro por linha e depois por coluna e vice-versa.)
(Sugestão: expresse o somatório de todos os elementos da matriz de incidência de duas maneiras diferentes, somando primeiro por linha e depois por coluna e vice-versa.)
Passo 1
O enunciado apresenta um grafo
Vamos interpretar a soma dos elementos na
-ésima coluna de
e usar isso para demonstrar o teorema 8.1.
Passo 2
Considere a soma dos elementos da
-ésima linha de
:
Cada coluna
que contribui com
corresponde a uma aresta que incide em
. Logo
isto é, a soma dos elementos da linha
é exatamente o grau do vértice
.
Passo 3
Agora olhe para a soma dos elementos da
-ésima coluna de
:
Arestas simples (sem laços) têm exatamente duas extremidades distintas, então para cada coluna
temos
Passo 4
Somando todos os elementos de
linha a linha, obtemos
Por outro lado, somando primeiro pelas colunas, dá
Como é o mesmo somatório, concluímos
Passo 5
Do fato de a soma dos graus ser
, um número par, segue que o total de vértices de grau ímpar também é par (pois só um número par de termos ímpares pode somar um número par). Essa é exatamente a afirmação do teorema 8.1.
Resposta
Somando a matriz de incidência por linhas obtemos
e por colunas obtemos
. Igualando,
, logo a soma dos graus é par, o que implica que o número de vértices de grau ímpar é par. Assim, o teorema 8.1 fica demonstrado.