Kssy escreveu: Seja G um grafo planar conexo com sequência de vértices (2, 2, 3, 3, 3, 4, 5).
Em quantas regiões qualquer representação plana de G divide o plano? Justifique.
Teorema do Aperto de Mãos: Seja G = (V, E) um grafo não orientado com
e arestas, então [tex3]2e=\sum_{v∈V}gr(v)[/tex3]
.
Seja G um grafo planar conexo com sequência de vértices (2, 2, 3, 3, 3, 4, 5).
Então temos 7 vértices de modo que:
[tex3]gr(v_1) = 2, \; gr(v_2) = 2, \; gr(v_3) = 3, \; gr(v_4) = 3, \; gr(v_5) = 3, \; gr(v_6) = 4, \; gr(v_7) = 5[/tex3]
.
Portanto, pelo Teorema, temos:
[tex3]2e=\sum_{v∈V}gr(v) \;\; \rightarrow \;\; 2e = (2+2+3+3+3+4+5) \;\; \rightarrow \;\; 2e = 22 \;\; \rightarrow \;\; e = 11[/tex3]
arestas.
Teorema de Euler: Seja G um grafo simples planar conexo com
e arestas e
v vértices.
Seja
r o número de regiões em uma representação planar de G.
Então, [tex3]r = e - v + 2[/tex3]
.
Portanto, pelo Teorema de Euler, temos:
[tex3]r = e - v + 2 \;\; \rightarrow \;\; r = 11 - 7 + 2 \;\;\rightarrow \;\; r = 6[/tex3]
regiões.