A connected graph that has no circuits or cycles is called a tree. In order for a connected graph to be a tree, it must have (n-1) edges where n is the number of vertices.
In this case, this connected graph has 68 vertices and 72 edges instead of just 67 edges which means that it does not qualify as a tree. So, if this connected does not qualify as tree, then it could have circuit or cycle.
By looking at the number of vertices and the number of edges, we can tell that this connected graph can have circuit because it has 4 more edges than vertices.
A certain connected graph has 68 vertices and 72 edges. Does it have a circuit? Explain.
1 answer
2 answers