Ensino Superior ⇒ Grafos

[Lucastadeu14]

HELP!!


1) Verifique se cada uma das afirmações abaixo é falsa ou verdadeira.
Se for falsa, dê um contra-exemplo, justificando. Se for verdadeira,
prove.
(a) Toda árvore com número par de vértices tem um número par de
folhas.
(b) Todo grafo bipartido com um número ímpar de vértices não é
hamiltoniano
(c) Se G é um grafo 5-regular e tem 10 vértices então G não é planar.

2. Considere o grafo G = (V, E), dado por:
V (G) = {a, b, c, d, e, f, g},
E(G) = {(a, b),(a, c),(b, d),((b, c),(c, d),(d, e),(d, g),(d, f),(e, f),(e, g),(f, g),(f, a)}.
(a) Desenhe G e desenhe também seu grafo complemento G.
(b) G é planar? Justifique.
(c) G é um grafo euleriano? Justifique.
(d) G é um grafo hamiltoniano? Justifique