Skip to content

Two-Terminal Series–Parallel Graph

A source–sink edge network built recursively from single edges by terminal-preserving series and parallel joins.

Version
v1 · 2026-10-03 · History
Domain-specific #
13682
Domain group
Formal Sciences
Origin domain
Mathematics
Subdomains
Graph Theory, Network Decomposition → Mathematics

Core Idea

A two-terminal series–parallel graph (TTSP graph) is an edge network with two distinguished vertices, source \(s\) and sink \(t\), obtained recursively from a single \(s\)–\(t\) edge. In a series join, one component's sink is identified with the next component's source, leaving the outer source and sink. In a parallel join, the sources of two components are identified and their sinks are identified. Repeating those two operations gives a construction tree for the whole network, not merely an impression that a drawing has some lines “in series” and others “in parallel.”[1]

The qualification two-terminal matters. The frozen source uses “series–parallel graph” in this rooted sense but also invokes the broader unrooted \(K_4\)-minor-free class. Every TTSP graph has controlled low-complexity structure, yet the absence of a \(K_4\) minor in an arbitrary graph does not, by itself, establish the given graph as a two-terminal series–parallel network for specified terminals. Wales's research exposition states a \(K_4\)-minor-free characterization with an explicit 2-connected qualifier. A three-leaf star illustrates why the unqualified equivalence fails: it has no \(K_4\) minor, but no pair of terminals can put all three leaf edges on source-to-sink paths.[1]

Structural Signature

Sig role-phrases: distinguished terminal pair → single-edge base → series join → parallel join → composition history; a quantity-specific combining rule is an application, not a membership axiom.

  • Distinguished terminal pair. The ordered or labeled source–sink interface fixes what is being connected. Change that interface and a construction valid for one choice need not remain valid for another. Treating a graph as unrooted erases a load-bearing part of this definition.[1]
  • Single-edge base. An edge whose endpoints are its terminals is the primitive network. The finite recursive definition begins here; a collection of vertices without the terminal edge is not an instance.[1]
  • Series join. Identify the sink of one TTSP component with the source of another while preserving the two outside terminals. This creates a common intermediate passage. The operation is available but need not occur in every member; a parallel join of two paths already gives an example without a top-level series join. Multigraph conventions also permit a network of parallel edges, whereas the cited simple-graph formulation restricts duplicate terminal edges.[1][2]
  • Parallel join. Identify both sources and both sinks of separate components. It creates alternative terminal-to-terminal subgraphs; a simple path with no parallel join also qualifies.[1]
  • Composition history. A parse tree records the successive joins and witnesses membership. It may not be unique, but at least one complete construction must account for every edge. Reversing the tree yields a series/parallel reduction sequence.[1]
  • Property-specific combining rule. When a property composes under both joins, the tree can evaluate it bottom-up: electrical resistance uses sum and reciprocal sum, while longest source-to-sink path length in a directed weighted acyclic instance uses sum and maximum. This role explains utility; it is not needed to decide graph membership.[3][2]

What It Is Not

  • Not every \(K_4\)-minor-free graph with forgotten terminals. A three-leaf star is \(K_4\)-minor-free but cannot be built as a two-terminal network for any two selected terminals: one leaf edge would lie outside every simple terminal-to-terminal route. The qualified 2-connected statement in Wales does not license the frozen seed's unrestricted equivalence.[1]
  • Not treewidth itself. Treewidth is a numerical graph invariant. A TTSP construction entails useful low-width behavior, but “treewidth at most two” does not supply designated terminals or a composition witness for a particular source–sink pair.
  • Not the same as a vertex-series-parallel digraph or precedence order. Valdes, Tarjan and Lawler explicitly distinguish vertex-series-parallel digraphs from edge-series-parallel multidigraphs in their recognition work. Which objects are vertices versus edges, and which operations are allowed, must be specified before identities or algorithms are transferred.[2]
  • Not any electrical network that contains a reducible corner. The entire two-terminal graph must have a valid reduction history. A subcircuit that happens to contain two series resistors does not make the whole network TTSP.[3]
  • Not an automatic fast algorithm for every question. The decomposition enables bottom-up computation only if the requested quantity has sound combine rules and the representation is supplied or found.[2]

Scope of Application

In electrical network analysis, the terminals are the two points across which equivalent resistance is requested. Each resistor supplies an edge; series joins carry the same branch current and add resistance, while parallel joins share voltage and add conductances. MIT's instructor-authored notes work a four-resistor two-terminal network by reducing a series pair, then a parallel combination, then a final series connection. The sequence is simultaneously a circuit calculation and a witness that the illustrated topology is TTSP.[3]

In algorithms and dependency modeling, a directed edge-series-parallel network can represent activities between start and finish events. If an edge has a duration and there is no resource contention, the longest start-to-finish path adds durations through series blocks and takes the larger duration through parallel blocks. This is a property of the directed weighted instance, not a claim that every TTSP graph is directed or that a real project with finite workers finishes at the critical-path lower bound. Original work on series-parallel digraph recognition also distinguishes edge and vertex constructions, so this entry keeps its edge-based scope explicit.[2][1]

Broader graph theory sometimes uses “series–parallel graph” for unrooted \(K_4\)-minor-free graphs or for graphs whose blocks can be treated through series–parallel structure. That is a neighboring convention, not an alias asserted here. The identity is intentionally named Two-Terminal Series–Parallel Graph to prevent a terminology choice from becoming a false theorem.[1]

Clarity

The construction test settles whether a network merely looks reducible or actually has a complete terminal-preserving parse. Drawings can hide which junctions are the same vertex and which branches share endpoints. Giving \(s,t\) and a binary series/parallel tree removes this ambiguity: each interior node declares exactly which endpoints are identified, and every leaf is one edge.[1]

It also separates a structural class from the quantity later evaluated on it. A resistor network and a duration-labeled activity graph may have the same parse shape but different algebra: reciprocal conductance combination versus maximum. Confusing their rules is not an error in recognizing TTSP membership; it is an error in transferring the application semantics.[3][2]

Manages Complexity

A network with many edges is replaced by a tree of small binary operations. At each node one can retain only the interface state needed for the target property. For equivalent resistance, a subnetwork can be summarized by one resistance between its terminals; for directed critical-path length, by one maximum duration between its terminals. The full interior wiring then matters through the construction tree rather than all at once.[3][1]

That compression has a price: terminal choice, edge labels and a valid algebra must remain visible. If a circuit is not wholly reducible, or if a scheduling model has resource conflicts across parallel branches, one scalar per subgraph may no longer answer the original question. A decomposition is a tool, not permission to suppress interactions that cross its boundary.[3][2]

Abstract Reasoning

To test an instance, designate its source and sink and seek a full recursive decomposition. A series split exposes an intermediate articulation through which every terminal route passes; a parallel split exposes two terminal-sharing subnetworks. Recur until every leaf is a single edge. A proposed split that leaves a dangling branch or a cross-link unaccounted for is not a proof of TTSP status. Conversely, a complete parse tree is a constructive certificate.[1]

Once certified, derive rather than guess an evaluation recurrence. For resistor networks, apply \(R_{\mathrm{series}}=R_1+R_2\) and \(R_{\mathrm{parallel}}^{-1}=R_1^{-1}+R_2^{-1}\) at the corresponding nodes. For a directed task-edge network with independent simultaneous branches, the longest route through series is \(L_1+L_2\) and through parallel is \(\max(L_1,L_2)\). The structure licenses these bottom-up steps only after the electrical or scheduling assumptions have been checked.[3][2]

Knowledge Transfer

The same base edge–series join–parallel join–terminal pair–parse tree structure transfers literally from a resistor network to an appropriately modeled directed activity-on-edge network. A decomposition tree can be reused as a shape while edge meanings and combining operators change. MIT's resistance sum/reciprocal law does not become a duration law; the max/plus recurrence for independent activities does not model resistance.[3][2]

Outside graph theory there is a broader compose-and-evaluate intuition, but treating it as an already recognized prime would require separate evidence across non-graph carriers. It is an explicit future-prime question. The current identity depends on graph edges, terminal identification and a graph construction, and remains domain-specific.

Examples

A reducible resistor network

MIT's 6.061 notes show a two-terminal four-resistor network whose right-hand pair is first combined in series. That result is combined in parallel with another branch, and the remaining outer resistor is finally added in series. The notes' final equivalent resistance is \(3\,\Omega\) for their chosen resistor values. Reversing the reductions constructs the original network from single-edge resistor units and demonstrates that the complete topology, not just one pair, is TTSP.[3]

Mapped back: distinguished terminal pair = the measurement input and return points; single-edge base = each resistor connection; series join = the right branch's pair and the final outer connection; parallel join = two branches sharing their entry/exit nodes; composition history = the reverse of MIT's three-step reduction; property-specific combining rule = additive series resistance and reciprocal parallel resistance.

A directed activity network with independent branches

Consider a constructed, not historically claimed, three-activity network: activity \(A\) lasts 2 time units from project start to a fork; \(B\) lasts 3 and \(C\) lasts 5 from that fork to the same finish event. Its edge-based parse is \(\operatorname{series}(A,\operatorname{parallel}(B,C))\). With unlimited capacity for \(B\) and \(C\) to run simultaneously, the longest directed start-to-finish path takes \(2+\max(3,5)=7\) units. A single-worker schedule would not enjoy that parallel execution; it is a different resource problem. The example applies the edge-series-parallel construction distinguished in graph-algorithm literature and a directly derived path recurrence.[1][2]

Mapped back: distinguished terminal pair = start and finish events; single-edge base = duration-labeled \(A,B,C\) arcs; series join = \(A\) followed by the fork–join block; parallel join = \(B\) and \(C\) share fork and finish; composition history = the stated parse; property-specific combining rule = sum then maximum under no resource contention.

Boundary: the three-leaf star

The undirected star \(K_{1,3}\) has no \(K_4\) minor and is tree-like. But any two chosen terminals leave a third leaf and its incident edge outside every simple source-to-sink route. Each edge of a TTSP graph lies on some terminal-to-terminal route by induction on the two constructors; the star therefore has no two-terminal series–parallel construction for its entire edge set. This missing composition history makes it a near miss, not an instance.[1]

Structural Tensions

T1 — Rooted constructive certificate versus broad minor shorthand. A TTSP parse identifies terminals and explains every edge. The easy phrase “no \(K_4\) minor” captures a related wider class but loses the terminal information, failing on \(K_{1,3}\). Diagnostic: Are both terminals fixed and every edge accounted for by the recursive construction, or has only an unrooted obstruction test been performed?[1]

T2 — Reusable decomposition versus property-specific algebra. The same parse can support resistance or path-length evaluation, but one uses sum/reciprocal and the other sum/max. A method that blindly transports a combining rule computes the wrong object. Diagnostic: What is the value stored at each subtree, and what law has been proved for each join?[3][2]

T3 — Parallel structure versus actual parallel execution. A directed fork creates two graph-theoretic branches. If resources are unlimited, critical-path duration takes their maximum; if one machine serves both, elapsed time may approach their sum. Diagnostic: Do shared resources or synchronization demands couple the branches beyond the graph's precedence edges?

Structural–Framed Character

This is a structural graph-class identity with an explicitly chosen interface. Evaluative weight: membership says nothing by itself about whether a circuit or schedule is good. Human-practice dependence: a modeler designates terminals and encodes connections, but a claimed parse can be checked as a graph fact once those data are fixed. Institutional origin: mathematical and engineering conventions choose the name and directed/undirected variants; no institution makes a nondecomposable graph decomposable by decree. Vocabulary travel: “series” and “parallel” cross circuits, tasks and flow, while edge identity and terminal gluing remain precise graph vocabulary. Import versus recognition: this class is recognized from a complete rooted construction; calling an arbitrary low-treewidth or \(K_4\)-free graph “TTSP” imports a broader label without the required witness.[1][2]

Its character: a domain-specific formal graph abstraction, not a prime. The more general recursively composable interface/evaluation skeleton is a future-prime question, not an asserted live parent.

Structural Core vs. Domain Accent

The core is two terminals → single-edge leaves → allowable series/parallel endpoint identifications → a complete finite construction of the network. Direction, edge weights, resistor physics and activity durations are domain accents or specialized variants. A quantity's bottom-up recurrence is important utility but not constitutive of TTSP membership: a graph can be TTSP even before any weights or evaluation problem are assigned.[1][3]

No strict DAG parent is staged. Live Treewidth is a numerical decomposition invariant, not a terminal-rooted graph constructor; live Directed Acyclic Graph excludes the undirected resistor instance and admits many non-series-parallel dependencies; live Electronic Circuit is a physical application rather than a formal graph genus. The broad unrooted \(K_4\)-minor-free class and vertex-series-parallel digraphs remain separate identity questions.

  • Related domain identity — Treewidth. TTSP networks have bounded-width structure, but the width number is not their recursive terminal construction.
  • Related prime — Directed Acyclic Graph. A directed TTSP activity network is acyclic under consistent edge orientation, but undirected TTSP resistor networks are not instances of that directed prime; no universal parent edge is asserted.
  • Related domain identity — Electronic Circuit. Some circuits instantiate the TTSP topology; bridge or other nonreducible circuits need not.
  • Related uncreated identity — unrooted \(K_4\)-minor-free graph. It should not be silently merged into this narrower TTSP node.[1]

Neighborhood in Abstraction Space

Two-Terminal Series–Parallel Graph sits in a moderately populated region (49th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Graph Structures & Combinatorial Objects (44 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With

  • The unrooted \(K_4\)-minor-free class. Tell: no \(K_4\) minor alone does not exhibit two terminals or an all-edge constructor history; \(K_{1,3}\) is the elementary counterexample.[1]
  • Vertex-series-parallel digraph. Tell: check whether vertices or edges are the compositional units and which transitive closure/reduction is being recognized.[2]
  • A graph with one reducible subnetwork. Tell: a partial series/parallel reduction does not prove the whole source–sink network reduces to one edge.
  • A generic DAG or precedence graph. Tell: a directed acyclic graph may contain cross-dependencies that have no edge-series/parallel parse.
  • A universal linear-time evaluator. Tell: recognition and a parse tree do not supply a sound recurrence for every graph property or account for limited scheduling resources.[2]

References

[1] Matthew Daniel Wales, Extremal Theory of Graph Minors and Related Topics, University of Cambridge PhD thesis (2022), Definition 6.12 and immediately following qualified \(K_4\)-minor discussion, PDF pp.106–107. https://api.repository.cam.ac.uk/server/api/core/bitstreams/3d97d7ca-dda0-4aa2-9c39-714492351124/content . registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t

[2] Jacobo Valdes, Robert E. Tarjan and Eugene L. Lawler, “The Recognition of Series Parallel Digraphs,” SIAM Journal on Computing 11(2) (1982), publisher abstract and keywords distinguishing vertex-series-parallel from edge-series-parallel multidigraphs. https://epubs.siam.org/doi/10.1137/0211023 . registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n

[3] MIT 6.061 Introduction to Electric Power Systems, instructor-authored Class Notes ch.1, “Serial and Parallel Combinations,” equations (6)–(8), Figure 11 and reduction on pp.4–6. https://www.ocw.mit.edu/courses/6-061-introduction-to-electric-power-systems-spring-2011/d79822ef5fbdb21b1c44e1b3b8282453_MIT6_061S11_ch1.pdf . registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k

[4] OpenStax, University Physics Volume 2, §10.2, Figure 10.15, a separate worked series/parallel equivalent-resistance reduction. https://openstax.org/books/university-physics-volume-2/pages/10-2-resistors-in-series-and-parallel . registry