Dada a matriz de incidência de um grafo, dê uma interpretação para a soma dos elementos da i sima linha e a soma dos elementos na j 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.)

Passo 1

O enunciado apresenta um grafo G\) com \(n\) vértices e \(m\) arestas e sua matriz de incidência \(A=(A_{ij})\) de tamanho \(n\times m\), onde \[A_{ij} = \begin{cases} 1, & \text{se o vértice }v_i\text{ é uma extremidade da aresta }e_j,\\\\ 0, & \text{caso contrário.} \end{cases}
Vamos interpretar a soma dos elementos na i\]-ésima linha e na \(j-ésima coluna de A e usar isso para demonstrar o teorema 8.1.

Passo 2

Considere a soma dos elementos da i-ésima linha de A:
\sum_{j=1}^{m}A_{ij}.
Cada coluna j que contribui com A_{ij}=1 corresponde a uma aresta que incide em v_i. Logo
\sum_{j=1}^{m}A_{ij} = \deg(v_i),
isto é, a soma dos elementos da linha i é exatamente o grau do vértice v_i.

Passo 3

Agora olhe para a soma dos elementos da j-ésima coluna de A:
\sum_{i=1}^{n}A_{ij}.
Arestas simples (sem laços) têm exatamente duas extremidades distintas, então para cada coluna j temos
\sum_{i=1}^{n}A_{ij} = 2.

Passo 4

Somando todos os elementos de A linha a linha, obtemos
\sum_{i=1}^{n}\sum_{j=1}^{m}A_{ij} = \sum_{i=1}^{n}\deg(v_i).
Por outro lado, somando primeiro pelas colunas, dá
\sum_{j=1}^{m}\sum_{i=1}^{n}A_{ij} = \sum_{j=1}^{m}2 = 2m.
Como é o mesmo somatório, concluímos
\sum_{i=1}^{n}\deg(v_i) = 2m.

Passo 5

Do fato de a soma dos graus ser 2m, 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 \sum_{i=1}^n\deg(v_i) e por colunas obtemos 2m. Igualando, \sum_{i=1}^n\deg(v_i)=2m, 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.