Paths, connectivity and cycles

Can you reach the laboratory in three steps?

Imagine six places: gate A, hall B, garden C, cafe D, laboratory E and cabin F. The only direct connections are AB, AC, BC, BD, CD and DE. Each connection can be used in either direction. The cabin has no connection in this model.

The route A,B,D,E takes three edges: AB, BD and DE. A,C,D,E takes three as well. There is no direct connection AE, so writing A,E does not create a one-step journey. Follow the listed connections rather than judging which circles look close in the drawing.

Use the preparation links for counting steps, stating definitions and checking a picture against its data. The preceding graphs lesson may provide extra practice when available; every required graph idea is defined here. No knowledge of a later algorithm or tree lesson is assumed.

On a first reading, follow the route comparisons, components and distance layers. Return to the loop-removal and bridge proofs after you can explain the six-place example. The proofs explain why the method works beyond this particular drawing.

State the graph and the route separately

A graph consists of a set V of vertices and a set E of edges. Here vertices name places, and an edge {u,v} records a direct connection. Braces indicate that {u,v} and {v,u} are the same undirected edge. Two vertices sharing an edge are adjacent.

This lesson uses finite simple undirected graphs: finitely many vertices, no edge from a vertex to itself, and at most one edge for each unordered pair of distinct vertices. A drawing represents that data. Line crossings create no new vertex unless one is explicitly named there.

A vertex sequence v₀,v₁,…,vₘ specifies a proposed route. It is a walk exactly when all its vertices belong to V and each consecutive pair is an edge. Its length is m, the number of edge steps, rather than m+1, the number of entries. Repeated entries still occupy positions in the sequence.

One existing vertex by itself is a walk of length zero. The empty sequence is not a walk here because it supplies no starting vertex. A sequence with a missing edge is not a walk, even if a different valid route connects the same endpoints.

Which repetitions are allowed?

A walk may repeat vertices and edges. A trail is a walk with no repeated edge. A path is a walk with no repeated vertex. Consequently every path is a trail, and every trail is a walk. The reverse implications need not hold.

In the same network, A,B,A,C,D is a walk but not a trail: AB is used again as BA, since direction does not create a different undirected edge. The sequence B,A,C,B,D is a trail: its edges BA, AC, CB and BD are all different. It is not a path because B appears twice.

A,B,D,E is a path because its four vertices are distinct. The single-vertex sequence F is also a path and a trail of length zero. A route need not use every vertex or every edge to be a path.

Terminology varies between books. Throughout this lesson path means all vertices in its sequence are distinct. A cycle is defined separately below and is not called a path under this convention. State the convention before comparing route labels.

Returning to the start is not enough

A closed walk has the same first and last vertex. A circuit here is a closed trail with at least one edge. A cycle is a closed walk of length at least three whose vertices, before the final return, are all distinct. In a simple undirected graph such a cycle uses different edges, so it is a circuit.

A,B,C,A is a cycle of length three. The final A records the return; no other vertex repeats. A,B,A is a closed walk of length two but not a circuit: it uses the same edge AB twice. It is not a cycle. A single vertex is a closed walk of length zero, but neither a circuit nor a cycle.

A circuit can pass through a vertex more than once. For example, two triangles sharing just one vertex permit a closed trail that goes around both triangles, revisiting the shared vertex. Such a circuit is not a cycle. Thus restrictions on edges and on vertices answer different questions.

A walk between two vertices contains a path

In the original network, A,B,C,B,D is a walk of length 4. The part B,C,B returns to B. Delete C and the later B, retaining the earlier B: A,B,D is a path of length 2. Edge BD still joins the retained prefix to D. The adjacent sequence diagram shows which occurrences are removed.

Suppose a finite walk from u to v repeats a vertex: positions i<j contain the same vertex. Delete the part after position i through position j. The retained prefix ends at that same vertex, so it can join the retained suffix using the suffix's original next edge. The endpoints stay u and v, including when a repeated endpoint is involved.

This deletion removes j−i edges, a positive number. Continue whenever a vertex repeats. Length cannot decrease forever below zero, so the procedure ends with a walk whose vertices are all distinct: a path with the same endpoints. If u=v, it ends with the length-zero path at u.

Therefore a walk exists between two vertices if and only if a path exists. The procedure does not promise a shortest path: deleting one chosen detour can leave other longer alternatives. It does prove that a shortest walk cannot contain a repeated vertex, because deleting such a detour would make it shorter.

Group vertices by where you can get

A vertex v is reachable from u when a walk, equivalently a path, goes from u to v. Every vertex reaches itself by the length-zero path. Reachability is symmetric in an undirected graph because a route can be reversed. It is transitive because two compatible walks can be joined; a repeated vertex in their joined walk can then be removed if a path is wanted.

A connected component is a maximal group of mutually reachable vertices. Maximal means every vertex reachable from a member is already in that group. Components partition V: each vertex belongs to one component, distinct components cannot overlap, and no edge joins different components. If two such groups shared a vertex, concatenate walks through that vertex to connect their members; maximality would make the groups the same.

Our network has components {A,B,C,D,E} and {F}. The isolated cabin is a component by itself. It cannot be reached from A, but it can be reached from F in zero steps. A failure to reach a destination is different from reaching it with distance zero.

Here a graph is connected when it has at least one vertex and exactly one component. Equivalently, it is nonempty and every pair of vertices is joined by a path. A singleton graph is connected. The graph with no vertices has no components and is not connected by our explicit convention; some texts use a different convention for that boundary.

Minimise a stated quantity

For reachable vertices u and v, the unweighted distance d(u,v) is the least number of edges in a u-to-v path. The minimum exists: lengths are nonnegative integers and at least one path exists. A shortest path has at most |V|−1 edges, since it cannot repeat a vertex. There can be several paths attaining the minimum.

In our network d(A,E)=3. Both A,B,D,E and A,C,D,E attain it. The route A,B,C,D,E has four edges and remains a valid path, but is longer. Also d(F,F)=0, while no finite distance from A to F is assigned because there is no path.

Distances count connections, not the drawn lengths of segments. If actual roads have unequal times or lengths, a minimum-edge route need not minimise those weights. Directed graphs also require checking allowed directions. Those different models are outside this lesson's unweighted undirected search.

Search all one-step extensions before two-step extensions

Start with layer L₀={A}. Put all previously unlisted neighbours of A into L₁={B,C}. Next inspect every vertex in L₁; its neighbours not in an earlier layer form L₂={D}. Continuing gives L₃={E}. No new vertex appears next, so the search stops. F has never appeared and is unreachable.

This procedure is breadth-first search. Keep each discovered vertex once, and record one vertex in the preceding layer that discovered it as a parent. Following parent links backwards constructs a path to the start. Neighbour order can change the chosen parent and which shortest path is returned; it does not change distances.

To justify the layers, suppose earlier layers contain exactly the vertices at their stated minimum distances. A newly added vertex in Lₖ₊₁ has an edge from Lₖ, so a route of length k+1 reaches it. It cannot have a shorter route: the penultimate vertex on a shorter route would already be in an earlier layer, and would have discovered it earlier. Conversely any vertex at distance k+1 has a penultimate vertex at distance k, so it will be added. Starting from L₀ proves the claim layer by layer.

When no new vertices remain, every neighbour of every reached vertex has already been reached. A walk from the start to an unreached vertex would have a first edge leaving the reached group, contradicting that closure. This proves unreachability rather than guessing it from the drawing. The finite search stops after at most |V| discoveries.

A cycle supplies an alternative around an edge

Connected and cyclic describe different properties. A line A–B–C–D–E is connected with no cycle. Our original network has cycles but is disconnected because F is isolated. A connected graph can also contain a cycle.

An edge is a bridge when deleting that edge, while retaining all vertices, increases the number of components. In the original network DE is a bridge: E loses its only connection. BC is not: after deleting it, B and C remain joined through A or D, and the two original components remain intact.

In a finite simple undirected graph an edge is a bridge exactly when it belongs to no cycle. If it lies on a cycle, the rest of that cycle joins its endpoints without that edge. Replace any use of the deleted edge by that alternative walk, preserving reachability. Deletion therefore cannot split a component.

Conversely, if the endpoints remain reachable after an edge is deleted, choose a path between them in the remaining graph. Restoring the edge closes this path into a cycle. The path has at least two edges, because a simple graph has no second edge between those endpoints. Thus an edge on no cycle has endpoints separated by deletion and is a bridge. This conclusion uses the stated simple undirected model.

Use an exact example to check your reasoning

Select a proposed route and predict its classification and destination reachability. Reveal the complete step table, components, minimum edge counts and all shortest paths for those endpoints. The outlined distance boxes are layers, not another geographic map. Simple cycles are listed once up to rotation and reversal, since they describe the same undirected cycle.

The supplied graphs have at most six vertices. Their finite inventories make exhaustive checking possible; the proofs explain the general finite-graph conclusions. An invalid proposed sequence does not erase a different valid path, and a valid sequence may end somewhere other than the requested destination. Check both the sequence and the question's endpoints.

Worked examples

Try it yourself

1. Why does A,B,D,E have length 3 rather than 4?

   Show the answer and reasoning

   It has four vertex entries and three consecutive edge steps.

   Edges AB, BD and DE are the three moves. Length counts moves, including any repetitions, rather than entries.

2. Is A,B,A a trail or cycle in the original undirected graph?

   Show the answer and reasoning

   Neither. It is a closed walk of length 2.

   AB and BA name the same undirected edge, so the edge repeats. A cycle here has length at least 3 and no repeated vertex before the final return.

3. Does A,E being an invalid proposed walk imply that E is unreachable from A?

   Show the answer and reasoning

   No. A,B,D,E and A,C,D,E are valid paths.

   The sequence A,E fails because edge AE is absent. Reachability asks whether any walk exists, not whether one chosen sequence works.

4. Two paths meet at their shared endpoint. Must their concatenation be a path?

   Show the answer and reasoning

   No; it is always a walk, but may repeat a vertex.

   In our graph, join the paths A,B,C and C,B,D. The concatenation A,B,C,B,D repeats B and edge BC. Loop removal leaves A,B,D.

5. A graph has vertices A,B,C,D,E and only edges AB and CD. List its components and decide whether it is connected.

   Show the answer and reasoning

   The components are {A,B}, {C,D} and {E}; the graph is disconnected.

   E is an isolated singleton component. No edge joins the three groups, so no walk connects vertices in different groups.

6. Under this lesson's convention, are a singleton graph and the graph with no vertices connected?

   Show the answer and reasoning

   The singleton is connected; the empty graph is not.

   The singleton has one component and a length-zero path from its vertex to itself. The empty graph has no component, and connected explicitly requires a nonempty vertex set.

7. Could a breadth-first search that inspects C before B give a different A-to-E shortest path? Could it give a different distance?

   Show the answer and reasoning

   It may choose A,C,D,E rather than A,B,D,E as its parent path. The distance stays 3.

   Both B and C occupy layer 1 and can discover D in layer 2. Parent tie choices do not change the first-discovery layer established by the distance proof.

8. Give a connected graph with no cycle and a disconnected graph with a cycle.

   Show the answer and reasoning

   The line A–B–C–D–E is connected and has no cycle. The original six-place graph has cycle A,B,C,A but isolated F makes it disconnected.

   Connectivity concerns every pair of vertices, while a cycle concerns a particular closed route. Neither observation supplies the other property.

9. Could an edge on a cycle be a bridge in a simple undirected graph?

   Show the answer and reasoning

   No. The rest of the cycle gives a route between its endpoints after deletion.

   Replace a use of the deleted edge by that alternative walk. Reachability within the original component is preserved, so deletion does not increase the component count.

10. A direct road takes 20 minutes; a two-edge route takes 5 minutes on each edge. Which route has fewer edges, and which is faster?

    Show the answer and reasoning

    The direct road has fewer edges, 1 rather than 2. The two-edge route is faster, 10 rather than 20 minutes.

    Unweighted distance optimises edge count. Unequal time weights define a different objective, for which this breadth-first distance result alone is insufficient.

What to carry forward

• A walk follows listed edges; a trail repeats no edge; a path repeats no vertex under the stated convention.
• A cycle returns only at the end and has at least three edges in a simple undirected graph; an out-and-back edge is not a cycle.
• Length-zero paths establish self-reachability, including for isolated vertices. An unreachable destination is different from distance zero.
• Connected components are maximal mutually reachable groups. A graph is connected here precisely when it is nonempty with one component.
• Breadth-first layers give minimum edge counts in an unweighted graph; different parent ties can produce different shortest paths.
• An edge is a bridge exactly when it lies on no cycle in the stated finite simple undirected model.