In a fibre backbone graph, what makes a site a cut vertex and a span a bridge?
answer
- single point of failure, two flavours
- removal raises the component count
- vertex version and edge version
- a bridge lies on no cycle
- high degree does not imply critical
basics
~20 sA cut vertex is a site whose removal, together with its spans, leaves the network in more pieces than before; a bridge is a span whose removal alone does that. Both name single points of failure.
solid answer
~40 sModel the backbone as an undirected graph: sites are vertices, spans are edges. A **cut vertex** (articulation point) is a vertex whose deletion, along with every span touching it, increases the number of connected components. A **bridge** (cut edge) is an edge whose deletion alone increases that count. Neither implies the other: two triangles of spans sharing one site have a cut vertex and no bridge, while two sites joined by a single span have a bridge and no cut vertex. For edges there is a clean characterisation — a span is a bridge exactly when it lies on no cycle, so no alternative route joins its ends. An audit reads the two lists differently: cut vertices are sites you cannot afford to lose, bridges are spans you cannot afford to lose.
code
pseudocode · 5 linesfor each span e = (u, v) in the network:
remove e
if u can no longer reach v using the remaining spans:
report e as a bridge
put e backgo deeper
Recall the two words and what each removal means: a cut vertex is a site, a bridge is a span, and both split the network when they go.
Explain the definitions in terms of the component count going up, and give the cycle test for a bridge: a span is one exactly when no cycle contains it.
Show you can read a real topology: produce the counterexamples in both directions, and say which of the two lists a proposed new span would actually shorten.
Frame it as spend: cycles are the unit of resilience, and site-level and span-level exposure are separate budgets that a single new link rarely reduces at once.
## The graph an audit actually draws A reliability review of a fibre backbone draws one **undirected graph**: every site is a **vertex**, every span of fibre between two sites is an **edge**. Undirected means a span carries traffic both ways, so "A reaches B" and "B reaches A" are the same statement. The review is not asking which route is fastest; it is asking which single loss leaves two sites unable to reach each other at all. Two single losses are possible, and they are different events: - a **site** is lost — the vertex disappears, and so does every span incident to it; - a **span** is cut — one edge disappears and both of its endpoints remain. Graph theory names each failure, and an audit needs both names. ## The two definitions - A **cut vertex**, also called an *articulation point*, is a vertex whose deletion together with all incident edges leaves a graph with **more connected components** than the original. - A **bridge**, also called a *cut edge*, is an edge whose deletion alone leaves a graph with **more connected components** than the original. "More components" carries the whole meaning. A **component** is a maximal set of sites that can still reach one another; if the count goes up, some pair that could reach each other no longer can. Nothing about traffic, capacity or commercial importance enters either definition — only reachability. The definitions are also a test: to decide whether span `e = (u, v)` is a bridge, delete it and ask whether `u` still reaches `v`. A linear-time sweep that finds every bridge at once exists, but it belongs to the traversal material rather than to the structure being defined here. ## A bridge is exactly a span on no cycle The characterisation worth memorising is cyclic: **an edge is a bridge if and only if it lies on no cycle.** Both directions are short: 1. If `e = (u, v)` lies on a cycle, the remainder of that cycle is a `u`–`v` route avoiding `e`. Cutting `e` changes nobody's reachability, so `e` is not a bridge. 2. If `e` lies on no cycle, then no `u`–`v` route avoids `e` — any such route together with `e` would close a cycle. Cutting `e` therefore separates `u` from `v`, so `e` is a bridge. Operationally: a span is a single point of failure exactly when it is not part of any ring. That is the structural reason ring topologies are bought. ## Neither condition implies the other | network | cut vertex? | bridge? | why | |---|---|---|---| | two triangles of spans sharing one site | yes, the shared site | no | every span lies on a triangle, so no span is cycle-free | | two sites joined by one span | no | yes, that span | deleting either site leaves one site, still one component | | a chain of sites in a line | every interior site | every span | nothing lies on a cycle | | every site joined to every other | none | none | any one loss leaves the rest fully joined | Two consequences follow, and the direction of each matters: - If a connected network with at least three sites has **no cut vertex**, then it has **no bridge** either: every site then has at least two spans, and a bridge endpoint with a second span would be a cut vertex. - The converse fails. **No bridges does not mean no cut vertices**, as the shared-site example shows. Eliminating every single-span failure does not eliminate every single-site failure. ## Degree is not the signal A common audit error is to rank sites by how many spans they terminate and call the busiest one critical. Criticality and degree are independent: - a hub terminating eight spans that all lead into a well-meshed core is **not** a cut vertex — its neighbours still reach one another without it; - a modest site with exactly two spans **is** a cut vertex when it is the only join between two halves of the network. The edge form of the same trap: the span carrying the most traffic is not a bridge unless it is the *only* route, while the quiet span out to a remote spur almost always is one. ## What the audit does with the two lists Cut vertices are sites that need a second independent presence, or whose dependants need re-homing. Bridges are spans that need a diverse second path. Funding one new span that creates a cycle through a bridge removes that bridge from the list, because the span now lies on a cycle; whether it also clears a cut vertex depends on which two sites the new span joins. Both lists shrink only as cycles appear — which is why redundancy is expensive. It is not bought as more capacity; it is bought as more cycles.
- Can a network have a cut vertex but no bridge at all?Yes. Take two triangles of spans sharing exactly one site. Every span lies on a triangle, so no span is a bridge, yet deleting the shared site leaves two separate triangles — it is a cut vertex. This is why a bridge-free design is not automatically a site-failure-tolerant design.
- Is every endpoint of a bridge a cut vertex?Only when that endpoint has at least one other span. In a network of two sites joined by one span, the span is a bridge, but deleting either site leaves a single site — one component, not more — so neither endpoint is a cut vertex. Degree-one endpoints never qualify.
- What single addition removes a given bridge from the list?Any new span that puts the old one on a cycle — that is, a span creating a second route between the two sides it used to separate. Adding a span between two sites already on the same side of the bridge changes nothing about it.
A cut vertex is the building's only stairwell: block it and the upper floors cannot reach the exit, however many doors each floor has.
saying these in an interview costs you the question
- Assuming the highest-degree site must be the cut vertex
- Calling the busiest span a bridge because it carries the most traffic
- Claiming both endpoints of a bridge are always cut vertices
- Believing a network with no bridges can have no cut vertex
- Deleting only one span when asked to delete a site