Chapter 11: Q2E (page 755)
Which of these graphs are trees?
Short Answer
\(\left( a \right)\)Tree \(\left( b \right)\)Tree \(\left( c \right)\)Not a tree \(\left( d \right)\)Tree \(\left( e \right)\)Not a tree \(\left( f \right)\)Tree.
Step by step solution
Over 22 million students worldwide already upgrade their learning with Vaia!
Definition
A graph is connected if there exists a path between every pair of vertices.
A simple path is a path that does not contain the same edge more than once.
A circuit is a path that begins and ends in the same vertex.
(a)
The given graph is a tree, because the graph is undirected (no arrows on the edges), connected (there exists a path between every pair of vertices) and contains no simple circuits.
(b) Checking whether it is tree or not
The given graph is a tree, because the graph is undirected (no arrows on the edges), connected (there exists a path between every pair of vertices) and contains no simple circuits.
(c) Checking whether it is tree or not
The given graph is a not a tree, because the graph is not connected. For example, there is no path between a and b.
(d) Checking whether it is tree or not
The given graph is a tree, because the graph is undirected (no arrows on the edges), connected (there exists a path between every pair of vertices) and contains no simple circuits.
(e) Checking whether it is tree or not
The given graph is a not a tree, because the graph is not connected. For example, there is no path between a and b.
(f) Checking whether it is tree or not
The given graph is a tree, because the graph is undirected (no arrows on the edges), connected (there exists a path between every pair of vertices) and contains no simple circuits.
