Problem 1: Let G = (V,E) be the following undirected graph: V = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, and E = {(1,5) , (1,3) , (7,1) , (5,7) , (3,7) , (3,8) , (8,7) , (9,7) , (7,2) , (4,9), (3,5) , (2,6) , (6,4), (5,10), (10,1)}.

a) Draw G, and give the adjacency matrix A of G.

b) Do a depth-first search (DFS) and a breadth-first search (BFS) on G, starting from node 1, and show the DFS tree and BFS tree. Tie-breaking is by choosing the smallest node.

c) Is G connected? How can you tell?

d) An articulation point (or single point of failure) of a connected graph is a node such that the removal of that nodes makes the graph disconnected. Does G have an articulation point? If so, which one(s)?

e) Does G have an Eulerian cycle? If yes, show such a cycle; if no, prove your answer.

f) Does G have a Hamiltonian cycle? If yes, show such a cycle; if no, prove your answer.