Project Description:

Consider a social network of 7 people, where each person is connected to at least four others. Draw a graph to represent this network, with the people as vertices and the connections as edges. Label the vertices with any number that represents distance between them. Answer the following questions. (Show the step taken clearly)

1. Starting from any of the vertices, find a Hamiltonian cycle for the graph.
2. Starting from the same vertex, find a Euler cycle and Euler path if they exist.
3. Apply Kruskal's algorithm to find the minimum spanning tree for the graph.
4. Does Kruskal's algorithm produce a minimum spanning tree of the graph? Justify your answer.
5. Use Dijkstra's algorithm to find the shortest path from one person to all other people in the network.
6. Find the minimum spanning tree by applying Prim’s algorithm of the social network.
7. Compare the properties of the graph you drew with those of a complete graph with 7 vertices.