Micro-questions over the graph fundamentals module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The core vocabulary
1. What is a vertex?
Answer
Also called a node — a point in a graph that can be connected to other points by edges. If the graph is a map, a vertex is a city.
2. What is an edge?
Answer
Also called an arc or link — a connection between two vertices. If a vertex is a city, an edge is a road.
3. What are endpoints?
Answer
The two vertices connected by a particular edge. Every edge has exactly two, and that fact gets used more often than you would expect.
4. What does incident mean?
Answer
The relationship between a vertex and an edge: if the vertex is an endpoint of the edge, the two are incident.
5. What does adjacent mean?
Answer
The relationship between two vertices connected by the same edge (or two edges meeting at the same vertex). Also called neighbours.
6. Why must you not use incident and adjacent interchangeably?
Answer
They relate different kinds of thing — incident is edge-to-vertex, adjacent is vertex-to-vertex. Textbooks and exam questions are strict about it.
7. What is the degree of a vertex, and what is the one exception?
Answer
The number of edges connected to it, written . The exception: a self-loop counts twice, because both its ends attach to the same vertex.
8. What are in-degree and out-degree, and when do they mean anything?
Answer
Edges coming in, and edges going out. They only mean something in a directed graph.
9. What is a self-loop?
Answer
An edge connecting a vertex to itself — a web page that links to itself.
10. What are parallel edges?
Answer
Multiple edges connecting the same pair of vertices — two separate roads between the same two towns.
11. What is a simple graph, and why does it matter?
Answer
No self-loops and no parallel edges. Most algorithms quietly assume they are given one, so it is worth checking your input really is simple before trusting them.
12. What is a multigraph?
Answer
A graph allowing both parallel edges and self-loops. Road networks and circuit diagrams usually are.
13. What is a weighted graph?
Answer
One where each edge carries a number — a distance, cost, capacity or travel time, depending on what you are modelling.
14. What are order and size?
Answer
Order is the number of vertices, ; size is the number of edges, . Often shortened to and .
15. What do dense and sparse mean, and what do they decide?
Answer
Dense: edges close to the maximum possible. Sparse: relatively few edges for the number of vertices. Which you have decides how you should store the graph — the whole subject of lesson 4.
B. The four dimensions
16. Name the four dimensions that must be fixed before choosing an algorithm.
Answer
Direction, weight, cycles, connectivity. Get one wrong and the algorithm you choose is wrong.
17. What does direction decide?
Answer
Whether an edge can be traversed both ways or only one.
18. Undirected vs directed — notation and meaning.
Answer
Undirected: , curly brackets — both ways; if you can get from to you can get back. Directed (digraph): , round brackets — to only, and it says nothing at all about going back.
19. Give the social media illustration of each.
Answer
Friendship is undirected — if I am your friend, you are mine. Following is directed — you following them does not mean they follow you.
20. What does weight decide?
Answer
Whether BFS suffices or you need Dijkstra.
21. What does “shortest path” mean in an unweighted graph? In a weighted one?
Answer
Unweighted: fewest edges, which BFS answers directly. Weighted: smallest total weight, a different question entirely — a route with more edges can easily be cheaper.
22. What does the presence of cycles force you to do?
Answer
Keep a visited set. Without one, a traversal goes round the cycle forever and never terminates.
23. What is a DAG, and what is it the shape of?
Answer
A directed acyclic graph. It is the shape of dependency — build steps, task schedules, course prerequisites, spreadsheet formulas.
24. Connected vs disconnected — and what does that force?
Answer
Connected: one traversal from anywhere reaches everything. Disconnected: a traversal only covers its own piece, so you must start a fresh traversal from each unreached vertex. Those pieces are connected components.
C. The handshake lemma
25. State the handshaking lemma.
Answer
In any undirected graph, the degrees sum to exactly twice the number of edges.
26. Why is it true?
Answer
Every edge contributes exactly two edge-ends, one at each endpoint, so summing degrees counts every edge twice. A self-loop puts both ends on the same vertex, which is why it adds 2 there.
27. What immediately follows about odd-degree vertices?
Answer
The number of odd-degree vertices is always even. The total is even and the even-degree vertices contribute an even amount, so the odd ones must pair up.
28. Can a graph have exactly three vertices of odd degree?
Answer
No — three is odd, and the count of odd-degree vertices must be even.
29. What is the maximum number of edges in a simple undirected graph on 6 vertices?
Answer
. In general — every pair joined once, no self-loops, no parallels.
30. And for a simple directed graph on vertices?
Answer
— each ordered pair once, because and are different edges.
D. The graph ADT
31. What is an ADT, and why read it before the code?
Answer
A description of what a structure does, written before deciding how to build it. The code answers “how”; the ADT answers “what” and “why”, and you cannot reliably work those out by reading an implementation.
32. Name the four building operations.
Answer
add_vertex(v), add_edge(u, v), remove_edge(u, v), remove_vertex(v).
33. What must remove_vertex(v) also do, and why is that not optional?
Answer
Remove every edge attached to it. An edge with only one endpoint is not a thing.
34. Name the query operations.
Answer
adjacent(u, v), neighbours(v), degree(v), vertices(), edges(), order(), size().
35. What two operations do weighted graphs add?
Answer
set_weight(u, v, w) and weight(u, v).
36. How do adjacent(u, v) and neighbours(v) differ as questions?
Answer
adjacent asks about one specific pair — “is there a direct flight from Lagos to Accra?”. neighbours asks for a whole list — “standing here, where can I go?”.
37. Why can no single representation make both cheap?
Answer
An adjacency matrix answers adjacent instantly but must scan a whole row for neighbours; an adjacency list is the other way round.
38. So what is “choosing a representation” really choosing?
Answer
Which of these operations you are willing to make slow — a choice you can only make once you know which ones your algorithm actually calls.
39. Which ADT operation do traversals actually run on?
Answer
neighbours(v) — which is why it is the one worth making fast.
40. Which algorithm wants edges() and never asks for neighbours?
Answer
Kruskal’s algorithm — it sorts the whole edge list and never asks a single vertex for its neighbours.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- What a Graph Is — the module
- Paths, Cycles and Connectivity — Question Bank — the next bank
- Graph Representations — where the ADT costs are tabulated
Software engineering
Infrastructure & security
Computer science
Hardware & engineering