A+ Answers

1. Let G be the graph given below.

(i) Determine the order and size of G.

(ii) Determine the neighborhood of vertex c.

(iii) Find the degree sequence of G

(iv) Is G an Eulerian graph? Explain.

(v) Is G a Hamiltonian graph? Explain.

(vi) Clearly, G is a planar graph. Verify Euler’s formula for G.

2. Let G be a graph on the vertices a, b, c, d, e, f, g, and h with adjacency matrix given by

(a) Draw the graph G:

(b) Is G an Eulerian graph? If it is, find an Eulerian circuit in G.

(c) Find the number of paths of length 5 from vertex c to vertex h.

5. Construct a graph whose adjacency matrix is given below by labeling the vertices (in alphabetical order) as a, b, c, d, and e. Verify the result of the Hand-Shaking Theorem for the resulting graph.