Problem 2053

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.