Graph basics II
Computer Science
Level
1
If
is a graph with 61 vertices and 60 edges, then:
is either a tree or is not a connected graph
doesn't have more than one path joining any two vertices
None of the choices are correct
is a tree
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Before I start, I would like to define a tree in graph theory:
A tree is an undirected graph with a set of vertices where by any pair of these vertices are connected by exactly 1 path. This also means that a tree does not have cycles (e.g. Triangle).
Then, if my graph has n vertices, the least number of edges I need to join up all the vertices is just n − 1 (to form a tree).
But suppose, I decide to create a cyclic sub graph along the way that would mean that I do not have enough edges to create a tree (since I only have n − 1 edges all of which are needed to create a tree). This means that without all the vertices connected, I will have a disconnected graph instead.
Hence the answer to this question is either a tree or a disconnected graph.