Universidade Federal do Espírito Santo
Teoria dos Grafos – Lista de Resultados
1. Seja G = (V,E) um grafo simples com n vértices e m
arestas. Então ∑vV d(v) = 2m
2. O número de vértices de grau ímpar, de um grafo G,
é par
3. O grau máximo de qualquer vértice em um grafo
simples com n vértices é n-1
4. O número máximo de arestas em um grafo simples
com n vértices é n(n-1)/2
22. As propriedades seguintes são equivalentes com
respeito à árvore:
a) G é um grafo conexo e acíclico;
b) G é acíclico e tem n-1 arestas;
c) G é conexo e tem n-1 arestas;
d) G é sem ciclos e por adição de uma aresta se cria um
único ciclo;
e) G é conexo mas G' = G – e é desconexo, e  E;
f) todo par de vértices de G é unido por um e só um
caminho simples.
23. Toda árvore é um grafo bipartido
24. O centro de uma árvore possui um ou dois vertices
5. |E(Kp,q)| = p*q
25. Todo grafo conexo possui uma árvore geradora
6. Um grafo G é desconexo sss V pode ser particionado
em dois subconjuntos V1 e V2 de maneira que não
existe aresta em G com um dos vértices extremos em
V1 e o outro em V2
7. Se um grafo (conexo ou desconexo) tem exatamente
dois vértices de grau ímpar, então existe um caminho
que liga esses dois vértices
26. Se G é conexo, então m  n-1
27. Seja T uma árvore geradora de um grafo conexo G
e seja a uma aresta de G, a T. Então T+ a contém um
único ciclo
8. Um grafo G é bipartido se e somente se não contém
ciclo ímpar
28. Uma árvore geradora T de um grafo conexo
valorado G é mínima sss não existe qualquer outra
árvore geradora de G, a uma distância 1 de T, cujo
peso é menor que o peso de T
9. Um grafo simples G com n vértices e k componentes
conexas pode ter no máximo (n-k)(n-k+1)/2 arestas
29. O algoritmo de Prim acha uma árvore geradora
mínima de um grafo conexo G não orientado
10. Um grafo conexo G é um grafo euleriano sss todos
os vértices de G são de grau par
30. Todo corte de arestas de um grafo conexo G deve
conter pelo menos uma aresta de toda árvore geradora
de G
11. Um grafo conexo G é um grafo euleriano sss ele
pode ser decomposto em ciclos
12. Seja w(G) o número de componentes conexas de G.
Uma ponte é uma aresta a tal que w(G - a) > w(G)
13. Uma aresta a é uma ponte de G sss não existir ciclo
em G contendo a
31. Em um grafo conexo G, qualquer conjunto minimal
de arestas contendo pelo menos uma aresta de
qualquer árvore geradora de G é um corte de arestas
32. Todo ciclo possui um número par de arestas em
comum com qualquer corte de arestas
33. Seja G (V,E) um grafo conexo, |V| > 2. Então:
14. Seja G = (V,E) um grafo com |V| = n e |E| = m.
2
Mostre que se G é um grafo bipartido então m ≤ n /4
a)
Um vértice v de V é articulação sss existem
dois vértices x e y em G, x, y  v, tais que todo
caminho entre x e y passa por v;
b)
Uma aresta {p,q} de E é ponte sss {p, q} for o
único caminho entre p e q em G
15. Se G é hamiltoniano então, para todo subconjunto
não-vazio e próprio S de V, w(G-S) ≤ |S|
16. Se G é um grafo simples com n  3 e d  n/2, então
G é hamiltoniano
17. Em um grafo completo com n vértices, existem (n1)/2 ciclos hamiltonianos com arestas disjuntas, se n é
ímpar e n  3
18. Um grafo T é uma árvore sss existir um único
caminho entre cada par de vértices de T
19. Se T é uma árvore então m=n-1
20. Toda árvore possui pelo menos duas folhas, n > 1
21. Um grafo conexo é uma árvore sss toda aresta é
uma ponte