1. (100 pts) Write a program to read a graph from a le and determine whether the graph is a tree or not. A sample graph is given below.
2 3 4
5 6
1
Figure 1: Graph representation
You can visually see that this graph is not a tree. To determine whether a graph is a tree you can use the following theorem.
Theorem: Any connected graph with n vertices and n-1 edges is a tree.
Above graph is connected. However, it has 6 vertices and 7 edges. So, it is not a tree. File format for this assignment is as follows
numofvertices numofedges
edge1
edge2
....
First line of the le contains the number of vertices and number of edges. Each edge is listed on one line with source vertex and destination vertex. Vertices start at 1. Edges are undirected and will be listed on the le once starting with the smallest vertex id. For example, for edges 2-5 and 5-2 the le will only have 2-5. But, you need to insert both to your adjacency list representation.
File for above graph is as follows
6 7
1 2
1 5
1 6
2 5
3 4
3 5
4 6
Sample execution of the program for the above graph is as follows
fox01 assign7 graph1.txt
The graph does not belong to a tree
