Micro-questions over the subgraphs and trees module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. Subgraphs
1. When is a subgraph of ?
Answer
When its vertices all come from , its edges all come from , and every edge it keeps still has both endpoints present.
2. Which condition do people forget, and why does it matter?
Answer
The dangling-edge condition. You cannot keep an edge whose endpoint you threw away — an edge with only one end is not a thing.
3. Summarise a plain subgraph in three words.
Answer
“Delete anything” — vertices, edges, or both, as long as nothing dangles.
4. What is an induced subgraph?
Answer
Pick a set of vertices ; keep every edge of with both ends inside . You have no choice about the edges — picking the vertices decides them. Written .
5. Summarise an induced subgraph in three words.
Answer
“Delete only vertices.”
6. What is a spanning subgraph?
Answer
Keep every vertex and delete only edges.
7. Summarise a spanning subgraph in three words.
Answer
“Delete only edges.”
8. What does the word “spanning” always mean?
Answer
Touches every vertex. Same meaning in “spanning subgraph” and “spanning tree”.
9. Induced vs spanning — what is the distinction people mix up?
Answer
They vary opposite things. Induced fixes the edges once you choose the vertices; spanning fixes the vertices and lets you choose the edges.
10. What is a clique, and what is the catch?
Answer
An induced subgraph where every pair of vertices is joined — everyone connected to everyone. Finding the largest clique is NP-hard, which is worth knowing before you try.
B. Trees and forests as graphs
11. What is a forest?
Answer
A graph with no cycles.
12. What is a tree, graph-theoretically?
Answer
A connected forest.
13. How does a forest relate to trees?
Answer
A forest is a disjoint union of trees, one per connected component.
14. What is conspicuously absent from the graph-theoretic definition?
Answer
No root, no parent, no children, no left and right. Just “connected and acyclic” — everything else is added later.
C. The six equivalent definitions
15. State all six equivalent definitions of a tree on vertices.
Answer
- Connected and has no cycles.
- Connected and has exactly edges.
- Has no cycles and has exactly edges.
- There is exactly one path between every pair of vertices.
- Connected, and removing any edge disconnects it — every edge is a bridge.
- Has no cycles, and adding any new edge creates exactly one cycle.
16. Why is having six equivalent definitions useful?
Answer
Whichever is easiest to check in your situation, you get the other five for free.
17. Give the intuition for why a tree has exactly edges.
Answer
Start with isolated vertices, so components. Every edge added without creating a cycle must join two different components, dropping the count by one. Going from components to 1 takes exactly such edges.
18. Which definition connects to data structures, and how?
Answer
Definition 4. Exactly one path between any two nodes is precisely what makes a tree navigable without a visited set — you can never come back to where you started, so there is nothing to guard against.
19. A connected graph has 7 vertices and 9 edges. Is it a tree?
Answer
No. A tree on 7 vertices has exactly 6 edges; 9 is three too many, so it contains cycles.
20. How many edges must you remove to make it one, and how many different results are possible?
Answer
Three — down to . Many different results are possible: you must break every cycle, and which edges you drop determines which spanning tree you end up with.
D. Spanning trees
21. What is a spanning tree?
Answer
A spanning subgraph that is a tree: all vertices, edges, no cycles.
22. Does every connected graph have one, and how do you build it?
Answer
Yes. Run BFS or DFS from any vertex and keep only the edges by which you first reached each vertex.
23. Why does that construction always work?
Answer
It produces edges — one per vertex except the start — and cannot contain a cycle, because each kept edge reaches a previously-unseen vertex.
24. How many spanning trees does the complete graph have?
Answer
, by Cayley’s formula. has 16; has 125.
25. What is the problem of choosing the cheapest one called?
Answer
The minimum spanning tree problem.
E. Back to the trees folder
26. What three things does the tree data structure add to the graph-theory tree?
Answer
- A root — one vertex singled out.
- An order on the children — which makes “left” and “right” meaningful.
- Values and an invariant — data plus a rule about how it is arranged.
27. What does rooting actually do to the edges?
Answer
It gives every edge a direction — away from the root — which is what finally makes the words “parent” and “child” mean something.
28. Map graph-theory degree onto rooted-tree vocabulary.
Answer
Degree = number of children for the parent, with the root having no parent.
29. Which rooted-tree words have no graph-theory counterpart at all?
Answer
Root, parent, child, sibling, subtree, level, height — all of them need the rooting first.
30. What does a degree-1 vertex correspond to?
Answer
A leaf — provided it is not the root.
31. Summarise the lesson in one sentence.
Answer
A tree is “connected and acyclic” six different ways, and everything you know about tree data structures comes from choosing a root and an order on top of that.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Subgraphs, Trees and Forests — the module
- Paths, Cycles and Connectivity — Question Bank — the previous bank
- Trees (data structure) — the same object, rooted
Software engineering
Infrastructure & security
Computer science
Hardware & engineering