Seja S um conjunto de vértices, S = {1,3,5,8}. Então
o(G – S) = 6, onde componentes ímpares de G-S={2}, {4}, {6}, {7}, {9}, {10}.
Pelo Teorema de Tutte, um grafo G tem 1-fator <=>
o número de componentes ímpares de G-S, para qualquer S de G, deve ser menor ou
igual o número de vértices de S.
Assim, como existe pelo menos um S tal que isto não é
verdade, então G não tem 1-fator.
Escolhendo um conjunto de vértices S com 5 vértices preenchidos
(na figura acima), tem-se 7 componentes ímpares (circuladas na figura acima).
Assim, pelo Teorema de Tutte não existe emparelhamento
perfeito, porque o(T-S) > |S|.
Como o grafo tem 16 vértices, o emparelhamento perfeito
teria 9 arestas. Como o grafo não tem emparelhamento perfeito, o emparelhamento
ilustrado na figura é máximo.
Número de componentes = 1.
Grau máximo = máx (grau máximo de G + |V(H)|, grau máximo
de H + |V(G)|).
Não foi resolvido em sala de aula no dia 23/09.