Elementos de Matemática Finita
Ficha 9 - Grafos
(Para apresentar na quarta-feira, dia 4 de Dezembro)
1. Seja G um grafo. Mostre que existem sempre dois vértices distintos v, w ∈ VG com o
mesmo grau. Construa um multigrafo com 4 vértices de graus todos distintos.
2. Considere as seguintes sequências de naturais. Verifique quais delas são gráficas
(sequência de graus de um grafo), e no caso afirmativo, desenhe um grafo com essa
sequência de graus.
(a) {3, 3, 2, 2, 2, 1}
(b) {6, 6, 6, 4, 4, 2, 2}
(c) {6, 6, 6, 6, 5, 4, 2, 1}
(d) {6, 6, 6, 4, 4, 3, 3}
3. O complemento de um grafo G é o grafo Ḡ com os mesmos vértices que G (VG = VḠ )
de forma a que v, w são adjacentes em Ḡ se e só se não são adjacentes em G.
(a) Se |VG | = n e G tem vértices com graus d1 , · · · , dn , quais os graus dos vértices de
Ḡ?
(b) Prove que se G não é conexo, então Ḡ é conexo. A afirmação recíproca é verdadeira?
4. Seja G um grafo com n vértices
e m arestas, e grau mínimo δ.
então G é conexo. Construa um grafo deconexo com
(a) Mostre que, se m > n−1
2
n−1
m= 2 .
(b) Mostre que, se δ > n2 − 1, então G é conexo. Construa um grafo deconexo com
δ = n2 − 1 (n par).
5. Determine o número de automorfismos dos seguintes grafos: (a) O grafo completo
de ordem n, Kn (b) O grafo ciclo de ordem n, Cn (c) Todos os grafos que se obtêm
de Kn eliminando 3 arestas. [Sugestão: há 5 casos possíveis; Note que qualquer
automorfismo de G induz um automorfismo de Ḡ]
6. Seja G um grafo com 10 vértices e 28 arestas. Prove que G contém um ciclo de
comprimento 4. [Sugestão: Comece por mostrar que há dois vértices v, w tais que
dv + dw ≥ 12]
7. Seja G um grafo bipartido com n vértices (isto é, V é a união disjunta, V = V1 ⊔ V2 ,
não há arestas entre os vértices de V1 6= ∅, nem entre os de V2 6= ∅, e há uma aresta
por cada conjunto {v1 , v2 } com v1 ∈ V1 e v2 ∈ V2 ). Mostre que
2
n
.
n ≤ |EG | ≤
4
8. Recorde que a excentricidade de um vértice v ∈ V num grafo G é o máximo e(v) =
max{d(v, w) : w ∈ V }, sendo o raio e o diâmetro de G, respectivamente o mínimo
e o máximo das excentricidades. Ou seja, r(G) = min{e(v) : v ∈ V }, D(G) =
max{e(v) : v ∈ V }. Mostre que
r(G) ≤ D(G) ≤ 2r(G).
9. Seja A a matriz de adjacência do grafo G, de vértices V = {v1 , · · · , vn }, e Ak = A · · · A
(k)
a sua k-ésima potência (k ∈ N). Denote por aij a entrada i, j da matriz Ak . Mostre
(k)
que aij é igual ao número de passeios diferentes, de comprimento k, entre vi e vj .
[Sugestão: Use indução, sendo o caso k = 1, a definição da matriz de adjacência].
10. Seja G conexo de diâmetro D e grau máximo ∆, e seja v ∈ V um dos vértices.
(a) Prove que o número de vértices à distância k de v é menor ou igual a ∆(∆ − 1)k−1
(b) Conclua a desigualdade
|V | ≤ 1 + ∆
(∆ − 1)D − 1
.
∆−2
11. Mostre que, num grafo conexo, quaisquer dois caminhos de comprimento máximo
têm sempre, pelo menos, um vértice em comum.
12. Seja G um grafo 4-regular (ou seja, dv = 4 para todo v ∈ V ). Mostre que podem
colorir-se as arestas de G com duas cores de modo a que em cada vértice incidem 2
arestas de cada uma das cores. [Sugestão: cada componente conexa de G é um grafo
euleriano com um número par de arestas]
13. Seja G um grafo conexo planar com n vértices e m arestas. Mostre que, se o menor
ciclo em G tem comprimento k, então
m≤k
n−2
.
k−2
14. Se G é planar com n ≥ 11 vértices, prove que o seu complementar não é planar.