Given below is information about a network. Choose one of the following three options: the network is definitely a tree; the network is definitely not a tree; the network may or may not be a tree . Accompany your answer with a brief explanation for your choice.
The network has 21 vertices and bridges.
Solution:-
A network is another name for a connected graph. Recall that a connected graph is a graph in which there is a path given from any vertex to any other vertex.
A tree is a network that has no circuits. Trees have three key properties that distinguish them from ordinary network. The first property is the single-path property, which states that in a tree, there is only one path connecting two vertices. The second property is the all-bridges property, which states that in a tree, every edge is a bridge, and that if every edge of a network is a bridge then the network must be a tree. The third property is the N-1 edges property, which states that a tree with N vertices has N – 1 edges, and that a network with N vertices and N – 1 edges must be a tree.
Determine which property is the most relevant for classifying the network.
The all-bridges property is the most relevant because the number of bridges is given.
In order to use the all-bridges property, first use the N – 1 edges property to determine how many edges a network with 21 vertices must have it if is a tree.
If a network has 21 vertices, it must have 21 – 1 = 20 edges if it is a tree.