Paths, cycles, connectivity & components
A walk becomes a path when no vertex repeats, and a cycle when it returns to its start with no other repeat. A graph is connected when a path joins every pair of vertices, and its components are the maximal connected pieces — exactly the equivalence classes of "is reachable from". Connectivity questions almost always reduce to counting components or finding a vertex whose removal increases that count.
✓ Unlimited questions · marked criterion by criterion · no card needed
Method: how to approach it
The order below is what examiners expect to see, and each step carries its own marks.
- Distinguish walk, trail, path, cycleWalks allow repeats; trails repeat no edge; paths repeat no vertex; cycles are closed paths of length ≥ 3 in a simple graph.
- Find components by explorationRun a depth- or breadth-first search from an unvisited vertex; everything reached is one component. Repeat until all vertices are visited.
- Use the edge boundA connected graph on n vertices has at least n − 1 edges. Fewer edges than that guarantees disconnection.
- Test for cut verticesRemove a vertex and recount components. An increase identifies a cut vertex (articulation point).
Worked example
A graph has 8 vertices and 5 edges. Show it cannot be connected, and find the minimum number of components.
- A connected graph on 8 vertices needs at least 8 − 1 = 7 edges.
- With only 5 edges it cannot be connected.
- Each component with kᵢ vertices needs at least kᵢ − 1 edges, so |E| ≥ n − (number of components).
- 5 ≥ 8 − c gives c ≥ 3.
Answer. It is disconnected, with at least 3 components — achieved, for example, by two triangles-worth of structure plus isolated vertices.
Where marks get dropped
These are the specific errors that cost credit on paths, cycles, connectivity & components questions — QED's rubric penalises each of them separately.
- Calling a repeated-vertex walk a path. The distinction matters in every proof about path lengths.
- Assuming a graph with many edges must be connected. A K₅ plus three isolated vertices has 10 edges and four components.
- Forgetting that a single vertex is a connected component on its own.
Practise this until it is automatic
Unlimited fresh questions
QED generates new paths, cycles, connectivity & components problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.
Marked like an examiner
Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.
Answer in real notation
A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.
Saved to your library
Every question you generate is kept and re-takeable as a timed exam, and your Graphs mastery is tracked so you know when this is exam-ready.
Paths, cycles, connectivity & components — frequently asked questions
How many edges force connectivity?
On n vertices, more than C(n−1, 2) edges guarantee it: the worst case packs all edges into a complete graph on n − 1 vertices, leaving one isolated.
What is a bridge?
An edge whose removal increases the number of components. An edge is a bridge exactly when it lies on no cycle.
How do I find components efficiently?
One DFS or BFS pass per component, giving O(V + E) overall. Union-find achieves the same incrementally as edges arrive.
The rest of Graphs
Terminology, connectivity, trees, paths and cycles. Each subtopic below has its own method, worked example and mark-losing traps.
- 1Degrees & the handshake lemma
- 2Paths, cycles, connectivity & components
- 3Trees & their properties
- 4Bipartite graphs & colouring basics
- 5Euler & Hamilton paths and circuits
- 6Adjacency matrices & isomorphism
- 7Degree sequences & graphic sequences
- 8Spanning trees: Kruskal & Prim
- 9Shortest paths with Dijkstra
- 10Planarity & Euler’s formula
- 11Directed graphs, in-degree & out-degree
- 12Binary trees: height, traversals & counting
- 13Chromatic number & colouring bounds
- 14Matchings & Hall’s marriage theorem
Ready to make paths, cycles, connectivity & components exam-proof?
Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.
Start practising free →