Practice question · True or false
A connected graph with 8 vertices and 8 edges must contain a cycle.
Hints
- How many edges does a tree on 8 vertices have?
- One more edge than a tree means one edge too many.
Show the answer
True
Why
True. A tree on n vertices has exactly n − 1 edges, so a connected graph with 8 vertices and 7 edges is a tree; the 8th edge joins two already-connected vertices and closes a cycle. Any connected graph with n or more edges is therefore cyclic, which is how cycle detection can start from a count.
Practise Graphs and Trees
The app has 4 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Graphs and Trees
- A social network is a graph, a filesystem is a tree, and a tree is a graph. What does the extra restriction…
- Select every statement that must be true of any tree with n vertices.
- Sort each term or description by what it is a property of.
- The handshaking lemma says the degrees of all vertices sum to twice the number of edges. Why must the total…