Separate local degree, reachability, and robustness to a link failure.
By the end: identify components and bridges without assuming that one-way reachability is mutual.
Reachability groups vertices
A vertex is reachable from a source when a permitted path connects them. In an undirected graph, reachability is mutual. Connected components are maximal groups of mutually reachable vertices. Maximal means no additional vertex can join the group while preserving that property, not that the group is the largest one.
A connected graph has one component. A graph with several components cannot carry a route between them. An isolated vertex forms its own component, even when it has no edges. Adding edges can merge components but cannot split them. Removing an edge may split a component or may leave an alternative route.
Build components from complete reachable sets
A connected component contains everything reachable from any one of its vertices, not merely the vertices visited by one chosen route. Use the fixed undirected graph with vertices A through F and edges AB, AC, BC, BD, CE, DE, EF. Starting at A, first collect B and C. Their connections add D and E, and E adds F. No further vertex remains to add. The full set is therefore one component. The route A, B, D is evidence for reaching D, but its three vertices are only part of that component.
Why does starting elsewhere give the same group? Undirected edges can be followed backward, so a route from A to D can be reversed. If D can reach another vertex, combining the reversed route with that onward route gives a walk from A to that vertex. Removing repeated portions gives a path. Consequently, two reachable sets cannot overlap at one vertex while disagreeing about which component contains that vertex. Any overlap would provide routes joining both groups. Components partition the vertices, meaning every vertex belongs to exactly one of the groups.
Reachability expands beyond one chosen route
Expansion
New vertices
Cumulative reachable set
Start
A
A
Follow edges from A
B, C
A, B, C
Continue from B and C
D, E
A, B, C, D, E
Continue from E
F
A, B, C, D, E, F
In the base graph, beginning at A reaches B and C, then D and E, then F. The rows show cumulative sets, not a timed simulation or the event order of the later search player.
To see maximality rather than size, retain six vertices but use exactly the edges AB, BC, CA, DE. The components are {A, B, C}, {D, E}, and {F}. The pair {D, E} is a component although another component is larger. Adding A to it would fail because A has no route to D or E. Conversely {A, B} is not a component because C can join while preserving mutual reachability. A maximal group cannot expand; a maximum-sized group is largest among the candidates. The two words express different claims.
An isolated vertex contributes a component because it is reachable from itself by a zero-edge path. That convention also handles a graph with vertices A, B, C and no edges. It has three components rather than zero. Component counting therefore requires the vertex list as well as the edge list. If an outage removes EF from the base graph, F remains a named site and becomes isolated. Deleting F from the records instead would answer a different question about a smaller set of sites. An absent link does not make its endpoints disappear.
One new undirected edge can merge at most two components. In the triangle, pair, and isolate example, adding CD merges {A, B, C} with {D, E}, but F remains separate. Adding EF then joins the last group. The two additions suffice to connect the graph, and fewer cannot suffice because one edge reduces the component count by at most one. More generally, connecting k initially separate groups requires at least k minus one new edges. This counts structural connections only; geographic feasibility and construction cost have not entered the question.
Two additions join three separate groups
Available edge set
Components
AB, BC, CA, DE
{A, B, C} | {D, E} | {F}
Add CD
{A, B, C, D, E} | {F}
Then add EF
{A, B, C, D, E, F}
Thin edges AB, BC, CA, DE initially form three components, including isolated F. Thick CD and EF are the two proposed additions. Each joins two previously separate groups, so the count falls from three to one. This is a paper example, not an editor preset.
A component is also a limit on possible route requests. If origin and destination are in different groups, no route exists under the recorded relation. Trying different intermediate stops cannot repair the missing connection. If they share a group, a route exists, but neither its length nor its cost follows from the component label. In the base graph A and F share a component even though they are not adjacent. Component membership answers whether any permitted path exists. Asking how short that path can be requires additional reasoning beyond the partition itself.
Direction changes connectivity
In a directed graph, a path from A to B does not imply a return path. A strongly connected component contains vertices that can reach one another in both directions. Weak connectivity ignores arrow directions. A weakly connected graph can have several strongly connected components.
For A to B, B to C, and C to A, all three vertices share one strong component. Adding C to D makes D reachable from them, but D cannot return. The graph remains weakly connected while D belongs to a separate strong component. Reducing each strong component to one vertex produces an acyclic graph.
Separate one-way reachability from mutual reachability
For directed edges, a list of reachable vertices depends on the starting point. Consider six vertices A through F and exactly the arrows A to B, B to A, B to C, C to D, D to C, D to E, E to F, F to E. Starting at A can reach all six. Starting at E can reach only E and F. Thus the set reachable from A is not automatically a strongly connected component. Its members must also be able to return to A, and C through F have no such return route.
The strong components in this example are {A, B}, {C, D}, and {E, F}. Each pair has arrows allowing a journey in both directions. The arrows B to C and D to E allow travel onward between groups, but no arrow chain returns to an earlier group. Notice that A can reach D even without an A-to-D edge. Strong connectivity concerns directed paths, which may have several steps, rather than requiring a direct arrow between every pair. A directed cycle through several vertices can provide mutual reachability without all possible direct connections.
A one-way chain connects three mutually reachable pairs
Starting vertex
Reachable vertices
Strong component
A
A, B, C, D, E, F
{A, B}
C
C, D, E, F
{C, D}
E
E, F
{E, F}
Arrowheads give the permissions. Opposite arrows are distinct curves. The complete edge set is A to B, B to A, B to C, C to D, D to C, D to E, E to F, F to E. One weak component contains three strong components.
Weak connectivity deliberately asks a different question by forgetting arrow directions. For the same six-vertex example, the undirected pairs become AB, BC, CD, DE, EF. This is one connected chain. The two opposite arrows between A and B become one undirected AB relation, not two parallel edges. The same merging occurs for CD and EF. Deduplicating those pairs preserves the simple-graph convention. The result establishes weak connectivity but cannot establish return journeys in the directed graph. Erasing arrows changes the permission rule, not just the way a picture looks.
Strong components still form disjoint groups. A vertex can reach itself. Mutual reachability is symmetric by its definition. It also passes through intermediate vertices: if A and B can reach each other, and B and C can reach each other, concatenate the appropriate directed routes to connect A with C in both directions. Repeated portions can be removed if a path is required. These facts explain why one vertex cannot belong to two different maximal strong components. They do not say that the ordinary reachable set from one source is such a component.
Replace each strong component by one group marker and retain arrows between different groups. In the example the result is {A, B} to {C, D} to {E, F}. There can be no directed cycle among these group markers. A cycle would let every group on it reach all the others and return, so they should have formed one larger strong component. This reduced graph records possible one-way movement between mutually reachable regions. Its arrows are schematic group relations, not new physical links between every pair of sites inside adjacent regions.
One return arrow merges all three strong components
The thin arrows are the previous chain's eight edges. Thick F to A closes a directed route through all three groups. Every vertex can now reach every other vertex. Adding A to F instead would not supply a return path. Curves and positions have no distance units.
Adding one carefully placed arrow can therefore have a larger effect than its local appearance suggests. Add F to A to the stated six-vertex directed example. From any group you can now continue around the chain and return through F to A. All six vertices become one strong component, even though only one arrow was added. Adding A to F instead would leave the three strong components unchanged, because that permission already follows through longer paths and supplies no return. These are paper comparisons. The connectivity widget below edits undirected edge removal, not directed arrows.
Inspect the graph and its result
Remove one connection
Original network
1 component. Bridge: E–F.
After removal
1 component: A, B, C, D, E, F.
Only the selected edge is removed; all six vertices remain. Blue reference edges are bridges. Colored selected vertices identify the component containing A, not a probability of failure.
Change to the base graph
Component count
No removal
1
Remove A-B
1
Remove E-F
2
E-F is a bridge. A-B has the alternate A-C-B route. Thick blue edges are the named selection; all original connections remain visible.
Use edge removal to distinguish bridges from alternate routes
The connectivity model preserves all six base vertices while removing at most one selected edge. Compare Keep all links with Remove A-B. Before removal, AB provides a one-step connection. After removal, A, C, B supplies a two-step replacement. Any longer route that formerly used AB can substitute this alternate path, reversing it when necessary. The result might repeat vertices, but repeated portions can be deleted without losing reachability. Thus losing AB can lengthen some routes without splitting the component. Connectivity survival does not promise unchanged journey length or unchanged cost.
The same replacement reasoning works for each edge lying on a cycle. AC has the alternate A, B, C, and BC has B, A, C. The cycle B, C, E, D, B supplies replacements for BD, CE, and DE. For instance, after deleting BD, B, C, E, D connects its endpoints. Every base edge except EF belongs to at least one of those cycles. Therefore each of those six single-edge removals leaves all vertices connected. The claim comes from explicit endpoint alternatives, not from the number of lines that happen to cross in the drawing.
After losing BD, a three-step replacement still connects its endpoints
BD is absent. Thick BC, CE, DE give B, C, E, D. The remaining thin edges are AB, AC, EF. All six vertices stay in one component, although the direct B-to-D step is no longer possible.
Now select Remove E-F. F has no other incident edge, so there is no way to replace that final step. The resulting components are {A, B, C, D, E} and {F}. All paths from any other vertex to F had to use EF. This makes EF a bridge in the original graph. The blue bridge marking in the reference concerns the original edge set, while the selected panel reports components after removal. Do not interpret an edge that is absent from the selected panel as an available alternate route or a surviving highlighted connection.
A bridge has an equivalent description through a cut. A cut divides the vertex set into two nonempty parts; its crossing edges have one endpoint in each part. For the split {F} and {A, B, C, D, E}, EF is the only crossing edge. Removing it leaves no route between the parts, since every such route must cross their boundary. Conversely, when deleting an edge splits a component, the resulting groups supply a boundary that this edge alone formerly crossed. A bridge is therefore a one-edge separation, not simply an edge drawn between distant clusters.
Consider the different split {A, B, C} and {D, E, F}. Exactly BD and CE cross it. Neither is a bridge in the original graph, because the other crossing remains after a single deletion. Removing both disconnects the two triples, with AB, AC, BC inside the first and DE, EF inside the second. The model removes only one edge at a time, so this two-edge comparison must be reasoned through on paper. It shows why no single-edge separation across a particular boundary does not mean that the boundary cannot be disconnected.
Two edges cross this cut; neither is originally a bridge
Removed edges
Crossing edges left
Components
None
BD and CE
1
BD
CE
1
CE
BD
1
BD and CE
None
2
The dashed boundary separates {A, B, C} from {D, E, F}. Exactly BD and CE cross it, shown thick. Removing either alone leaves the other. Removing both separates the two triples. The boundary is a partition marker, not a wall or an edge.
The location of vulnerability can change after an initial failure. After removing BD alone, CE becomes the sole crossing edge of that same split and hence a bridge in the remaining graph. DE also becomes a bridge there because D then has only its connection to E. EF remains a bridge. In contrast, the surviving triangle near A still provides alternatives for AB, AC, and BC. Bridge status belongs to a specified graph state. A report should distinguish original bridges from bridges created by a prior removal rather than treating the original markings as permanent properties of physical link names.
A bridge is a structural vulnerability
An undirected bridge is an edge whose removal increases the number of components. An edge on a cycle is not a bridge because the rest of that cycle supplies an alternative route. Conversely, if an edge has an alternate path between its endpoints, that path plus the edge forms a cycle. This explains the bridge test through cycles.
A bridge identifies vulnerability to that modeled edge's loss, not a probability of failure. A graph without bridges can still fail through two simultaneous losses or a shared physical cause. Vertex failure is a different test: deleting one site also removes all of its incident edges. An articulation vertex is one whose removal increases the component count.
State whether the failed object is an edge or a vertex
Deleting a site is different from deleting one connection. A vertex failure removes that vertex and every edge incident to it. In the base graph, removing E deletes CE, DE, and EF together. The surviving vertices are A, B, C, D, F, with edges AB, AC, BC, BD. A through D remain connected, while F is isolated. There are two components instead of the original one. E is therefore an articulation vertex. This definition compares component counts before and after vertex removal; it does not keep the failed site as an isolated survivor.
Removing F gives a different outcome. Its only incident edge EF disappears, and the remaining five vertices stay connected. The component count stays one, so F is not an articulation vertex, despite being an endpoint of a bridge. Removing B also leaves a connected graph, since A connects through C to E and E connects to D and F. Checking the other vertices shows that E is the only articulation vertex of the base graph. A low degree, a bridge endpoint, and an articulation vertex are related observations but are not interchangeable labels.
Removing E removes three incident edges at once
Failure operation
Surviving components
Remove vertex E
{A, B, C, D} | {F}
Remove vertex F
{A, B, C, D, E}
Remove edge EF
{A, B, C, D, E} | {F}
The surviving vertices are A, B, C, D, F; E is absent rather than isolated. Only AB, AC, BC, BD survive. F is still present and isolated, so the remaining graph has two components. Removing only EF would instead retain E and its other connections.
Edge redundancy can coexist with a single vulnerable site. Use five vertices A, B, C, D, E and exactly the edges AB, BC, CA, AD, DE, EA. Every edge belongs to one of the two triangles, so deleting any one edge leaves the graph connected. Nevertheless, deleting A leaves two components, {B, C} and {D, E}. Both triangles rely on the same shared vertex to communicate. This graph has no bridge but does have an articulation vertex. A claim about surviving any single link loss therefore cannot silently expand into a claim about surviving any single site loss.
The successful single-edge checks have a precise logical scope. For every edge in the stated graph, remove that edge alone and verify that the remaining vertices stay connected. This establishes a conditional guarantee for that set of separate cases. It does not give the chance that a link fails, the chance that two links fail together, or how long repair takes. In a real network, distinct graph edges might share a power source, road crossing, or cable conduit. One physical event could then remove several modeled edges, so the physical failure cases differ from the tested cases.
Even a complete list of surviving connections can leave service questions unanswered. Removing AB from the base graph preserves reachability between every pair, but a trip formerly using AB may require extra steps. If links have capacities, an alternate route might not carry all displaced traffic. If directions or schedules matter, an undirected availability edge might grant travel that actual operations forbid. None of these possibilities refutes the component calculation. They show which conclusion it supports. The result certifies a route under a binary undirected relation, not travel time, throughput, or uninterrupted real service.
No bridge does not mean no vulnerable vertex
Failure on this graph
Remaining components
Connected?
AB alone
{A, B, C, D, E}
Yes
AD alone
{A, B, C, D, E}
Yes
Vertex A
{B, C} | {D, E}
No
Two triangles share only A. Every edge has an alternate route around its triangle, so any one edge loss is survivable. Removing A simultaneously removes AB, AC, AD, AE and leaves the separate edges BC and DE. This is a structural comparison, not an outage probability.
To assess an unfamiliar network claim, first fix the surviving vertex set and the exact failure operation. Then seek either a separation with no surviving crossing edge or explicit alternate routes for the affected connections. For vertex loss, inspect all incident edges together rather than selecting only one. This method makes a counterexample checkable from endpoint records. The base graph supplies a one-edge counterexample to universal link resilience and a one-vertex counterexample to universal site resilience. Estimating real outage risk would additionally require measured failure data and shared-cause assumptions, neither of which is supplied by these constructed examples.
Exercises
One-way exit
A, B, and C form a directed cycle, and C has an edge to D. List the strong components and explain why D is not in the first.
Hint
A return path is required, not just an arrival.
Worked answer
Start group
Can reach other group?
A, B, C
Yes, via C to D
D
No return path
A one-way connection does not merge strong components. Thick blue edges are the named selection; all original connections remain visible.
The strong components are {A, B, C} and {D}. The cycle gives mutual reachability among the first three. D has no outgoing edge and cannot return to any of them. Ignoring directions would put all four in one weak component.
Triangle reliability
Each of three sites connects to both others. Does having no bridge prove the network survives every outage?
Hint
Compare one edge loss with two losses at the same site.
Worked answer
Failed edges in triangle
Connected?
A-B only
Yes, through C
A-B and A-C
No, A is isolated
Structural redundancy is not an empirical reliability estimate. Thick blue edges are the named selection; all original connections remain visible.
It survives any one modeled edge loss: the remaining two edges still connect all sites. Losing both edges incident to one site isolates it. A shared cable duct or power supply might cause such correlated losses. The no-bridge result is conditional on a single-edge failure model.
Sources and further reading
Selected reference passages support the definitions and algorithms below. The networks, explanations, and implementations are original. Terminology and assumptions are stated within each lesson; source review is not an independent audit of this course. Optional links are not runtime dependencies.
Graph representations, degree, trees, BFS and DFS. This course explicitly reserves path for a walk without repeated vertices; the reference uses a different path convention.
Directed reachability, strong components, DAGs, and topological orders. The lesson uses zero-indegree removal rather than the reference implementation's reverse-postorder method.