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
  1. Connected and has no cycles.
  2. Connected and has exactly edges.
  3. Has no cycles and has exactly edges.
  4. There is exactly one path between every pair of vertices.
  5. Connected, and removing any edge disconnects it — every edge is a bridge.
  6. 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
  1. A root — one vertex singled out.
  2. An order on the children — which makes “left” and “right” meaningful.
  3. 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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Graphs