Some graphs let you get from anywhere to anywhere else, and some don't. That single yes-or-no question -- is the graph connected? -- turns out to be one of the most load-bearing ideas in the whole course: it's the first thing to check before running a shortest-path algorithm, before asking whether a spanning tree even exists, before anything about flow or matching makes sense.
Picture a graph as a map of towns and the roads directly connecting them. A connected graph is a map where you can drive from any town to any other, possibly through several others along the way. A disconnected graph is really several separate maps that happen to share one page -- there's simply no road, of any length, between a town on one map and a town on another. Each of those separate maps is a component: not just "a bunch of towns you can reach," but every town reachable from any starting point in that piece, no more and no fewer.
Connectedness is a graph's property of having a path between every pair of its vertices; a graph is connected exactly when that property holds. When it isn't, the graph breaks apart into pieces called components: components are maximal sets of vertices, each internally connected to every other vertex in the same set, with no path at all crossing between two different sets. "Maximal" is the word doing the real work in that definition -- a component is not just some connected piece, it is the largest connected piece containing a given vertex, so no two distinct components can share a vertex or be merged into one without adding an edge that doesn't exist.
Every graph decomposes into components uniquely: an isolated vertex with no edges at all is still a component, just a component of size one, and a fully connected graph is the special case of exactly one component containing every vertex.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
A graph has 10 vertices and forms exactly 1 component. What can be concluded?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Edge count is not fixed by having one component -- many different edge counts can still yield a single connected component.
A single component does not require the specific cycle shape -- many different connected shapes qualify.
Why
Exactly one component is precisely the definition of a connected graph.
From Discrete Mathematics I — Logic, Proof, and Structure
A graph is called connected when what is true?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Degree at least 1 does not guarantee every pair can reach each other -- two separate connected pairs could still form two components.
Having no cycles is unrelated to connectedness -- a graph can be connected or disconnected regardless of cycles.
Why
Connected means a path exists between every pair of vertices, no exceptions.
From Discrete Mathematics I — Logic, Proof, and Structure
Can an edge ever connect two vertices that belong to two different components of the same graph?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Size is irrelevant -- an edge between two vertices always forces them into the same component, by definition.
Direction does not change this -- an arc between two vertices still links them into one reachable group.
Why
Components are defined as the maximal groups connected by paths -- an edge between two vertices is itself a path, so it would merge them into one component.
Build a connected graph
Toggle edges until every one of the five vertices can reach every other. Then remove one edge -- does the graph stay connected?
Loading interactive…
Worked example
Counting components in a small graph
-
1
A graph has vertices A, B, C, D, E and edges AB, BC, DE. How many components does it have, and which vertices belong to each?
-
2
Start from any vertex and trace every vertex reachable from it: from A, the edges AB and BC reach B and C, and no edge from A, B, or C leads anywhere else.
-
3
That's one component, \{A,B,C\}. Repeat from any leftover vertex: D reaches E via DE, and nothing further.
-
4\boxed{\text{2 components: } \{A,B,C\} \text{ and } \{D,E\}}
Loading interactive…
Worked example
Deciding what one added edge can and can't fix
-
1
A graph has three components: \{A,B\}, \{C,D,E\}, and \{F\}. Adding a single new edge, what's the fewest components the graph can have afterward?
-
2
One new edge has exactly two endpoints, so it can join at most two of the three components together into one.
-
3
Any third component left untouched by that edge stays exactly as separate as before -- one edge simply cannot reach a component it doesn't touch.
-
4\boxed{2 \text{ components} - \text{one edge merges two pieces, the third stays on its own}}
Loading interactive…
Worked example
Recognizing an isolated vertex as its own component
-
1
A graph on vertices A, B, C has edges AB only -- C has no edges at all. Is C part of the same component as A and B, or is something else going on?
-
2
Check whether any path connects C to A or B: with zero edges touching C, no walk of any length can start or end there and reach anywhere else.
-
3
C is therefore its own maximal connected piece, even though that piece contains only one vertex and no edges.
-
4\boxed{2 \text{ components: } \{A,B\} \text{ and } \{C\}}
An isolated vertex is not "not in a component" -- it's a perfectly valid component of size one, by the same maximality rule that governs every larger one.
Where this shows up
Epidemiology and social networks
A contact-tracing network built from who has been near whom is only useful for predicting spread within a single component: an outbreak that starts in one component of the contact graph structurally cannot reach a person in a different component through this network at all, no matter how many links away it seems, since no path connects the two pieces. Public health teams use exactly this connectedness check to decide which parts of a population share any exposure risk in the first place.
Check your understanding (counts toward your progress)
A social network's graph has 4 components. What does this say about the people in two different components?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
The graph only records the specific relationship being modeled -- it can't speak to every fact about two people.
Geography isn't something a component structure encodes by itself.
Relative group sizes aren't implied by the component count alone.
Why
Being in different components means precisely that no path -- direct or through any number of intermediate people -- connects them within this graph.
Stick strictly to what a component records -- reachability through the modeled relationship -- rather than any real-world fact the graph doesn't encode.
A graph has 10 vertices split into components of sizes 4, 3, 2, and 1. How many components does the graph have in total?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Count the listed pieces directly: four separate component sizes are given, so there are 4 components (the sizes happen to sum to the 10 total vertices, as a check: 4+3+2+1=10).
Correct answer
Also accepted:
Why
Count the separate component sizes listed, rather than adding them together.
A graph has exactly one component. A single edge is then removed. What is the largest possible number of components afterward?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Removing an edge can split the graph, so 1 isn't always guaranteed to remain the answer -- but check what the true ceiling is.
A single removed edge has only two endpoints, so it can separate the graph into at most two pieces, never three.
The number is bounded, not unlimited -- think about how many pieces one missing connection can actually create.
Why
Removing one edge can disconnect its two endpoints from each other at most -- splitting the graph into at most 2 components, never more, since only one connection was ever removed.
Think about how many pieces a single removed edge, with only two endpoints, could possibly separate a graph into.
Compare that ceiling against each of the answer choices offered.
What is a component of a graph?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
'Any connected subgraph' is too loose -- a single edge inside a bigger connected piece is connected but isn't the whole component.
Components have nothing to do with cycles specifically -- a component can be cycle-free.
A single edge is far smaller than a component in general.
Why
The word 'maximal' is essential: a component is the largest connected piece containing a given vertex, not just any connected chunk inside it.
Practice: Connectedness and counting components (4 problems · doesn’t affect your progress)
A graph is connected. How many components does it have?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A connected graph is, by definition, one single maximal connected piece.
1
A graph has 3 separate triangles, sharing no vertices or edges with each other. How many components does it have?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Each triangle is internally connected and shares no path to the others -- three separate maximal pieces.
Correct answer
Also accepted:
Why
A graph has 2 components. One edge is added between a vertex in the first and a vertex in the second. How many components remain?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The new edge directly connects the two previously-separate pieces, merging them into one.
Ask what a single edge crossing between two components does to those two specific pieces.
1
A connected graph has a bridge (an edge whose removal disconnects the graph). What happens to the component count if that bridge is removed?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A bridge's defining property is that removing it splits the graph into exactly two pieces -- no more, no fewer.
Recall the defining property of a bridge -- exactly what happens to the graph when it's removed.
Use that defining property directly, rather than considering the full range of possible outcomes.
It becomes exactly 2