Network Topology

Every two-terminal element becomes one branch, regardless of what it is. Five resistors plus one source:

A 6 Ω resistor and an 8 V source are the same object here — a line joining two dots. Topology cannot tell them apart, and does not need to.

The number of independent loops:

Exactly the three meshes Set 4 used. Problem 12 proves this formula rather than quoting it.

Identifying the graph. Four nodes, and every pair of them joined by exactly one branch: \(\binom{4}{2} = 6\) branches. This is the complete graph \(K_4\).

Note what the drawing loses and keeps. Bending branch 6 into an arc is not a change of circuit — the graph is defined by which nodes each branch joins, not by where the lines are drawn. Two drawings that look nothing alike may be the same graph.

A subgraph is a tree if it (i) is connected, (ii) touches every node, and (iii) contains no loop. Checking branches \(\{1,3,5\}\):

A single path visiting all four nodes: connected \(\checkmark\), touches every node \(\checkmark\), no loop \(\checkmark\). The three chosen branches are the twigs.

The co-tree is everything left over — branches 2 \((a\!-\!d)\), 4 \((c\!-\!b)\) and 6 \((b\!-\!a)\), called the links:

Why a tree must have exactly \(n-1\) branches. Start with one node and no branches. Each branch added to a tree must reach a node not yet included — otherwise both its ends are already in the tree, and a loop is formed. So each branch adds exactly one node, and reaching all \(n\) nodes from the initial one requires exactly \(n-1\) branches.

Two consequences follow at once. A tree with fewer than \(n-1\) branches cannot reach every node, so it is disconnected; one with more must contain a loop. Both bounds are tight, which is what makes the count exact rather than approximate.

Build the Laplacian \(\mathbf{L}\): diagonal entry \(L_{kk}\) is the number of branches at node \(k\), and \(L_{jk} = -1\) if nodes \(j\) and \(k\) are joined. Every node of \(K_4\) has degree 3:

Every row sums to zero, so \(\mathbf{L}\) is singular — as it must be, since the count cannot depend on which node is deleted.

The matrix-tree theorem states that the number of trees equals any cofactor of \(\mathbf{L}\) — that is, the determinant after deleting any one row and the matching column. Deleting the first of each:

Cayley's formula gives the number of trees of a complete graph on \(n\) nodes directly:

A useful sub-count: of these 16, exactly 8 avoid the source branch 6 and so are trees of the five-resistor sub-network alone. Deleting a branch from \(K_4\) leaves a graph whose Laplacian cofactor is 8.

Entry \(a_{jk}\) is \(+1\) if branch \(k\) leaves node \(j\), \(-1\) if it enters, and 0 if the branch does not touch the node. Rows are nodes \(a, c, d, b\):

Property 1: every column sums to zero. A branch has exactly two ends, so it leaves one node and enters another, contributing one \(+1\) and one \(-1\):

Property 2: the rows are linearly dependent. Because every column sums to zero, adding all \(n\) rows gives the zero row:

So \(\operatorname{rank}(\mathbf{A}_a) \le n-1 = 3\), and for a connected graph it is exactly \(n-1\) (Problem 19 proves the converse).

Deleting any one row gives the reduced incidence matrix \(\mathbf{A}\), of full rank \(n-1\). Deleting the row for node \(b\) — that is, choosing \(b\) as the reference:

Take row \(j\) of \(\mathbf{A}_a\) and multiply it into the branch-current vector \(\mathbf{i} = (i_1,\dots,i_b)^{\mathsf T}\). The entries are \(+1\) for branches leaving node \(j\) and \(-1\) for those entering, so the product is

One row is one node equation. Collecting all \(n\) rows gives \(\mathbf{A}_a\mathbf{i} = \mathbf{0}\).

Now the independence question. The number of independent equations in a linear system is the rank of its coefficient matrix, and Problem 4 established

Hence exactly \(n-1\) node equations are independent — the number asserted without proof throughout Sets 3, 6 and 7.

What the redundancy means physically. The dependence is \(\sum_j (\text{row } j) = \mathbf{0}\), so adding all \(n\) node equations gives \(0 = 0\). Charge that leaves any node must arrive at another; once \(n-1\) nodes balance, the last is forced.

Verifying on the bridge with the branch currents of Sets 2 and 4, in amperes:

Node \(d\) gives \(-0.4167 - 0.0833 + 0.5 = 0\;\checkmark\), and node \(b\) then follows automatically: \(-0.5 - 0.5 + 1 = 0\).

Removing one twig from a tree splits its nodes into two groups. The fundamental cutset of that twig is the set of all branches — twig and links alike — joining one group to the other. Since only one twig can be involved, each cutset is identified by its twig.

Twig 1 \((a\!-\!c)\). Removing it separates \(\{a\}\) from \(\{c,d,b\}\). Which other branches cross that divide? Branch 2 \((a\!-\!d)\) and branch 6 \((b\!-\!a)\):

Twig 3 \((c\!-\!d)\). Removing it separates \(\{a,c\}\) from \(\{d,b\}\). Crossing branches: 2 \((a\!-\!d)\), 4 \((c\!-\!b)\), and 6 \((b\!-\!a)\):

Twig 5 \((d\!-\!b)\). Removing it separates \(\{a,c,d\}\) from \(\{b\}\). Crossing branches: 4 \((c\!-\!b)\) and 6 \((b\!-\!a)\):

Now the matrix, with rows ordered by twig and columns by branch. Orient each cutset in the direction of its own twig; entries are \(\pm1\) according to whether a branch crosses with or against that direction:

Ordering the columns twigs-first makes the structure explicit:

The identity block appears because each twig lies in its own cutset and no other — which is exactly what guarantees the \(n-1\) cutset equations are independent, since no row can be built from the others.

A tree has no loops, so adding any one link creates exactly one — the fundamental loop of that link, consisting of the link plus the unique tree path joining its two ends. Orient each loop along its own link.

Link 2 \((a\!\to\!d)\). The tree path from \(d\) back to \(a\) runs \(d \to c \to a\), traversing branch 3 backwards and branch 1 backwards:

Link 4 \((c\!\to\!b)\). Path from \(b\) back to \(c\) runs \(b \to d \to c\), traversing 5 backwards and 3 backwards:

Link 6 \((b\!\to\!a)\). Path from \(a\) back to \(b\) runs \(a \to c \to d \to b\), all three twigs forwards:

Assembling, with columns ordered twigs then links:

Each link appears in its own loop and no other, giving the identity block — and with it, independence of the \(b-n+1\) loop equations.

KVL in matrix form. Row \(m\) of \(\mathbf{B}\) dotted with the branch-voltage vector \(\mathbf{v}\) sums the voltages round loop \(m\), with signs given by the traverse direction:

Checking with the bridge's branch voltages \(\mathbf{v} = (3.5,\, 5,\, 1.5,\, 4.5,\, 3,\, -8)^{\mathsf T}\) V, in branch order 1 to 6:

Take row \(m\) of \(\mathbf{B}\) (loop \(m\)) and row \(j\) of \(\mathbf{A}\) (node \(j\)). Their inner product is

A term survives only where branch \(k\) lies in loop \(m\) and touches node \(j\).

Now count. A loop is a closed walk, so it either misses node \(j\) altogether — in which case every term is zero — or passes through it exactly once, entering by one branch and leaving by another. Exactly two terms survive.

Suppose the loop enters node \(j\) along branch \(p\) and leaves along branch \(q\). Entering means the traverse direction agrees with the branch pointing into \(j\), so \(b_{mp}a_{jp} = -1\); leaving gives \(b_{mq}a_{jq} = +1\). Whatever the individual signs, the two terms are opposite:

This holds for every loop and every node, so \(\mathbf{B}\mathbf{A}^{\mathsf T} = \mathbf{0}\) identically. Nothing about tree choice, planarity or element values entered the argument.

Verification on the bridge. Take \(L_6 = (1,1,1,0,0,1)\) in branch order and the row of \(\mathbf{A}\) for node \(c\), which is \((-1,0,1,1,0,0)\):

Loop \(L_6\) enters \(c\) by branch 1 and leaves by branch 3; the two contributions cancel and everything else is zero. All nine entries of the product vanish.

What it means. KCL forces \(\mathbf{i}\) into the null space of \(\mathbf{A}\), of dimension \(b - (n-1) = l\). KVL forces \(\mathbf{v}\) into the row space of \(\mathbf{A}\), of dimension \(n-1\). These two subspaces are orthogonal complements in \(\mathbb{R}^b\):

Three facts, each already established. KCL: \(\mathbf{A}\mathbf{i} = \mathbf{0}\) for the source-free part, or \(\mathbf{A}\mathbf{i} = \mathbf{i}_s\) with injected currents. Ohm's law branch by branch: \(\mathbf{i} = \mathbf{G}_b\mathbf{v}\). And branch voltages from node voltages:

The last is the matrix form of "branch voltage = potential at the tail minus potential at the head", and it is where the transpose enters.

Substituting each into the next:

The symmetry and diagonal dominance asserted in Set 6, Problem 19 are now immediate. For any vector \(\mathbf{x}\),

A sum of positive conductances times squares. So \(\mathbf{Y}\) is symmetric positive semi-definite for any network of positive resistors — and positive definite when the graph is connected, guaranteeing a unique solution.

Applying it to the bridge. Take \(\mathbf{G}_b = \operatorname{diag}(\tfrac16, \tfrac1{12}, \tfrac1{18}, \tfrac19, \tfrac16, 0)\) — the source branch carries no conductance — and \(\mathbf{A}\) from Problem 4. Multiplying out:

Rows and columns for nodes \(a, c, d\). Note \(Y_{aa} = \tfrac16 + \tfrac1{12} = 0.25\) and \(Y_{ac} = -\tfrac16\) — exactly the "by inspection" rules of Set 6, produced here by matrix multiplication rather than assertion.

The 8 V source fixes \(V_a = 8\), so delete that row and move its column to the right-hand side:

Precisely Set 6, Problem 16, and hence the same 83.3 mA in the 18 Ω arm.

The argument is Problem 9 with every word dualised. KVL: \(\mathbf{B}\mathbf{v} = \mathbf{0}\), or \(\mathbf{B}\mathbf{v} = \mathbf{v}_s\) with source rises. Ohm's law: \(\mathbf{v} = \mathbf{R}_b\mathbf{i}\). And branch currents from loop currents:

This last equation is the whole justification for loop analysis: any current of this form automatically satisfies KCL, since \(\mathbf{A}\mathbf{i} = \mathbf{A}\mathbf{B}^{\mathsf T}\mathbf{I}_l = \mathbf{0}\) by the orthogonality of Problem 8.

Substituting:

With \(\mathbf{R}_b = \operatorname{diag}(6, 12, 18, 9, 6, 0)\) and \(\mathbf{B}\) from Problem 7:

Only loop \(L_6\) contains the source, and it traverses it as a rise.

Solving:

Recovering the branch currents from \(\mathbf{i} = \mathbf{B}^{\mathsf T}\mathbf{I}_l\):

The source carries 1 A, so \(R_{ab} = 8/1 = 8\ \Omega\), and the 18 Ω arm carries 83.3 mA — the same two numbers Sets 2, 4 and 6 produced.

The comparison is the point. Set 4's mesh matrix was

A different matrix entirely — and note the \(+18\) off-diagonal above, impossible for uniformly clockwise meshes. The loop currents differ too. Yet every branch current agrees to the last digit.

The sum in question is an inner product of the branch-voltage and branch-current vectors:

Substitute \(\mathbf{v} = \mathbf{A}^{\mathsf T}\mathbf{V}_n\) from Problem 9:

Three lines. KVL supplied the first substitution, KCL killed the middle factor, and nothing else was used.

Verification on the bridge, with the sign convention that \(v_k\) and \(i_k\) follow the same branch orientation:

The five resistors absorb 8 W between them and the source delivers 8 W — conservation of energy, recovered as a special case.

The surprising form. The proof used \(\mathbf{A}\) only. So if two different networks share the same graph, the voltages of one and the currents of the other still satisfy the relation:

Replace all five bridge resistors with capacitors, inductors or diodes and drive it with an arbitrary waveform: the products of those currents with the original DC voltages still sum to zero.

The quantities being summed are not powers of anything — they mix one network's voltage with another's current — so this is not energy conservation. It is a statement about topology, which is why it survives non-linear and time-varying elements untouched.

KCL count. From Problem 5, the node equations are the rows of \(\mathbf{A}_a\), and the number of independent ones is its rank. Problem 4 established \(\operatorname{rank}(\mathbf{A}_a) = n-1\):

KVL count. From Problem 7, the fundamental loops number one per link, and \(\mathbf{B} = [\mathbf{B}_t \mid \mathbf{I}]\) contains an identity block, so its rows are independent:

Why no more exist. The two subspaces of Problem 8 are orthogonal complements in \(\mathbb{R}^b\), so their dimensions must sum to \(b\). Having found \(n-1\) and \(b-n+1\), which already sum to \(b\), no further independent equation of either kind can exist:

The count matches the unknowns. There are \(b\) branch currents to find. Kirchhoff's laws supply exactly \(b\) independent equations — no fewer, so the circuit is solvable; no more, so it is not over-determined. That the two match is not a coincidence but a consequence of the orthogonal-complement structure.

Checking against the sets already worked:

In each case mesh analysis used the KVL count and nodal the KCL count, and Set 4, Problem 7's advice — compare the two and pick the smaller — is now visible as a comparison of two subspace dimensions.

A graph is planar if it can be drawn on a plane with no two branches crossing. The test is on the graph, not on a particular drawing: a drawing with crossings proves nothing until every alternative has been ruled out.

Is \(K_4\) planar? Yes. The drawing in Problem 1 has no crossings, which settles it — redraw the bridge with \(c\) and \(d\) inside the triangle \(a\!-\!b\) and all six branches lie flat. That is exactly why Set 4 could use meshes on it.

Kuratowski's theorem. A graph is non-planar if and only if it contains a subgraph that is a subdivision of either

"Subdivision" means branches may be split by extra nodes in series without affecting the result. These two graphs are the only obstructions there are.

Why mesh analysis needs planarity. A mesh is defined as a loop with no other loop inside it — a window in a plane drawing. The definition refers to the drawing, so without one the concept does not exist. Note that the count \(l = b - n + 1\) remains perfectly valid; what fails is the identification of those \(l\) loops with windows you can point at.

Why nodal analysis does not. Nodes and branches are defined by the incidence matrix alone, which records only which node each branch touches. Nothing in \(\mathbf{A}\mathbf{G}_b\mathbf{A}^{\mathsf T}\) refers to a drawing, so it is constructed identically for planar and non-planar graphs.

Loop analysis via a tree also survives, since the fundamental loops of Problem 7 are found by tracing tree paths — no drawing required. What is lost with planarity is only the convenience of reading the loops off a picture.

The construction. Place one node of the dual graph inside each mesh of the original, plus one in the outer region. For every branch of the original, draw one dual branch crossing it and joining the two dual nodes on either side. The result is the dual graph.

The counts transform predictably. Each mesh becomes a node and each node a mesh, while branches map one-to-one:

So a circuit needing 3 mesh and 4 nodal equations has a dual needing 4 mesh and 3 nodal — the counts swap exactly.

The element dictionary follows from the branch correspondence, since a branch shared by two meshes becomes a branch between two dual nodes:

The worked example. A series loop \(V\!-\!R\!-\!L\) has one mesh, so its dual has two nodes: one inside, one outside. All three branches cross between them, giving three parallel branches:

The governing equations confirm it. The original obeys

Identical in form with every symbol replaced by its dual. Any result proved for one is thereby proved for the other, which is why the series and parallel \(RL\) and \(RC\) circuits of Set 18 need be solved only once.

Counting elements: one source, three series resistors, three shunt resistors.

The nodes are the reference rail, the source's top terminal, and the three junctions along the ladder — but the source's top terminal and the first series resistor's left end are the same point, giving \(n = 5\).

Hence

Three meshes, as Set 4 used; four node equations, of which the source fixes one, leaving the three unknowns of Set 6.

A natural tree. Take the source branch and the three series resistors as twigs — a path from the reference up through the source and along the ladder, touching all five nodes with four branches:

Each shunt resistor is a link, and its fundamental loop is exactly one rung of the ladder — the mesh set recovers itself.

Why tridiagonal. Each rung touches only the rungs immediately before and after it, so meshes 1 and 3 share no branch:

Every non-zero off-diagonal entry corresponds to a shared branch, so the sparsity pattern of the matrix is the adjacency structure of the graph.

The same holds nodally: node 1 connects only to node 2, node 2 to nodes 1 and 3, and so on, giving another tridiagonal matrix — which is why Set 6's ladder solution eliminated so cleanly from the far end back, and why the assumed-current method of Set 2 worked at all.

The formula. For a network of resistors, with the source branch removed,

where \(W\) sums, over every spanning tree, the product of the resistances not in that tree; and \(W_{ab}\) sums, over every two-component spanning forest that puts \(a\) and \(b\) in different components, the product of the resistances not in that forest.

The five-resistor bridge has eight spanning trees, each of three branches, leaving two excluded:

Only 8 of the \(\binom{5}{3} = 10\) three-branch subsets are trees; the two triangles \(\{6,12,18\}\) and \(\{18,9,6\}\) contain loops and are excluded.

Now the two-component forests separating \(a\) from \(b\). Each has two branches, leaving three excluded:

The ratio:

Exactly the value delta–wye gave in Set 2, mesh analysis in Set 4, nodal in Set 6, and loop analysis in Problem 10 — reached this time without solving a single simultaneous equation.

When it is worth using. Almost never for computation: the number of spanning trees grows so fast that \(K_6\) already has 1296. Its value is theoretical. Because both sums have positive terms, \(R_{ab} > 0\) always; and because increasing any resistance increases some terms of \(W_{ab}\) at least as fast as those of \(W\), no resistance increase can ever lower \(R_{ab}\) — Rayleigh's monotonicity law, obtained by inspection of a formula.

Every pair of five nodes is joined once:

The three counts:

Why mesh analysis is unavailable. \(K_5\) is the smallest non-planar graph — one of the two Kuratowski obstructions of Problem 13. Any drawing has at least one crossing, so there are no windows to call meshes. The number 6 is still correct as a count of independent loops; what is missing is a way to identify them by eye.

Loop analysis still works, because a tree can be chosen without any drawing. Take any four branches forming a path through all five nodes as twigs; the remaining six links each close one fundamental loop, and \(\mathbf{Z} = \mathbf{B}\mathbf{R}_b\mathbf{B}^{\mathsf T}\) follows as in Problem 10.

Nodal wins decisively: four equations against six, and no topological difficulty. Set 4, Problem 7 advised nodal as the safe default on unfamiliar topologies; this is the case that advice was aimed at.

A quick check that the counts are consistent: \((n-1) + l = 4 + 6 = 10 = b\;\checkmark\), exactly as Problem 12 requires. Non-planarity costs the mesh method but leaves the arithmetic of topology untouched.

Why sparse. From Problem 9, \(Y_{jk} \ne 0\) only when nodes \(j\) and \(k\) are joined by a branch. Real circuits have bounded fan-out — a node meets perhaps three to six elements, whatever the total size — so the number of non-zeros grows linearly with \(n\):

A million-node integrated circuit gives a matrix with a few million non-zeros out of \(10^{12}\) entries — a density around one in a million.

What fill-in is. Eliminating node \(k\) connects every neighbour of \(k\) to every other. In graph terms, the elimination deletes node \(k\) and adds a clique on its neighbours:

If \(Y_{jm}\) was zero and both factors are not, a new non-zero appears where the circuit had no branch. That is fill-in, and it is pure cost.

Why ordering matters. Consider a star: one central node joined to \(n-1\) others. Eliminate the centre first and its \(n-1\) neighbours all become mutually connected — the matrix fills completely. Eliminate the outer nodes first and there is no fill-in at all, since each has only one neighbour.

Same circuit, same matrix, same answer — and a difference of several orders of magnitude in time and memory, decided entirely by the sequence in which nodes are eliminated.

What is actually done. Finding the ordering that minimises fill-in is NP-hard, so simulators use heuristics: minimum degree eliminates the node with fewest neighbours next, and nested dissection recursively splits the graph along small separators. Both are graph algorithms operating on the structure of this set, run before any numerical value is looked at.

If connected, the rank is \(n-1\). Problem 4 gave \(\operatorname{rank} \le n-1\). For the reverse, take any tree — one exists precisely because the graph is connected — and consider the \(n-1\) columns of \(\mathbf{A}_a\) belonging to its twigs. Remove a leaf node of the tree: its single twig is the only branch touching it, so that column has exactly one non-zero entry. Deleting the pair and repeating shows the twig columns are independent, giving \(n-1\) independent columns.

If disconnected, the rank is lower. Suppose the graph falls into \(s\) parts with \(n_1, \dots, n_s\) nodes. No branch joins one part to another, so \(\mathbf{A}_a\) is block-diagonal after reordering:

Each block is the incidence matrix of a connected graph, of rank \(n_p - 1\). Ranks of block-diagonal matrices add:

So the rank detects the number of parts, and the case \(s = 1\) recovers \(n-1\). The two directions together give the "if and only if".

The loop count is unaffected in form. The general result, valid for any \(s\), is

A forest of \(s\) trees has \(n-s\) twigs, so the links number \(b - n + s\). Every formula in this set is the special case \(s = 1\).

What it means for a circuit. A disconnected circuit is \(s\) independent circuits, each solvable alone. The complication is that node voltages are then determined only within each part: one reference node is needed per part, and the potential difference between two parts is undefined, since no branch connects them.

This is not a curiosity. A transformer, an optocoupler and a relay all couple two circuits with no conductive path, so their graphs have \(s = 2\). Simulators require an explicit reference in each isolated part, and reporting "singular matrix — node has no DC path to ground" is exactly the detection of \(s > 1\).

Each method chooses which subspace of \(\mathbb{R}^b\) to parameterise, and how:

Superposition and supermesh are the same operation. Both add rows. Adding two rows of \(\mathbf{A}\) gives a generalised KCL over a surface enclosing two nodes — a supernode; adding two rows of \(\mathbf{B}\) gives a KVL round a path avoiding a shared branch — a supermesh. Set 7, Problem 2 and Set 5, Problem 2 both proved this by hand.

What is genuinely different. Only two things:

Everything else — the sign conventions, the symmetry rules, the by-inspection shortcuts, the special handling of sources — follows from those two choices.

What is not different. The branch currents and voltages. Sixteen trees, three or more methods, and one answer, because all of them solve \(\mathbf{A}\mathbf{i} = \mathbf{i}_s\) and \(\mathbf{B}\mathbf{v} = \mathbf{v}_s\) subject to the element laws — a system with a unique solution whenever \(\mathbf{A}\mathbf{G}_b\mathbf{A}^{\mathsf T}\) is non-singular.

What this does not cover. Topology is silent on element values, so it cannot tell you which method will be less arithmetic in a given case, and it says nothing about dependent sources — which break the symmetry of both matrices without altering the graph at all. Set 4, Problem 20 and Set 6, Problem 9 remain the authorities there.