Graph theory fundamentals

The formula (the core equation(s), each with a one-line reading of what it says)

G = (V, E)     a set of vertices V and a set of edges E, each edge joining two vertices

Reads: a graph is nothing but a parts list and a connection list — no positions, no lengths, no geometry unless you add them back deliberately.

deg(v) = number of edges touching vertex v

Reads: degree is the connection count at one node — pin count on a connector, port count on a switch, branch count at a pipe tee.

Handshaking lemma:   Σ deg(v) = 2·|E|

Reads: summing every node's connection count tallies each edge exactly twice — so the total is always even, and the number of odd-degree vertices is always even.

Adjacency matrix:    A[i][j] = 1 if vertices i and j share an edge, else 0
Walk counting:       (A^k)[i][j] = number of length-k walks from i to j

Reads: the wiring diagram becomes a square of numbers, and raising that square to a power counts every k-hop route through the network — connectivity turned into arithmetic.

Adjacency list:      for each vertex, the list of its neighbors
Storage:             matrix ~ |V|² cells;   list ~ |V| + 2·|E| entries

Reads: the matrix pays for every possible connection; the list pays only for the ones that exist.

Complete graph:      |E| = n·(n−1)/2

Reads: the worst case — everything talks to everything — grows with the square of the node count, which is why full-mesh anything stops scaling fast.

Where you meet it (2-4 concrete engineering situations, specific: bench, test stand, review board)

The schematic on your second monitor. A netlist is a graph and always has been: component pins are vertices, nets are edges. When the ECAD tool flags an unconnected pin, it is reporting a degree-zero vertex. Nodal analysis — the method inside every SPICE run — is built on the same node-and-branch structure Kirchhoff formalized, and the solver's matrix is the circuit's graph wearing numbers.

The test stand cable database. Four racks, three patch panels, 400 channels, and a spreadsheet that claims to describe them. Model it as a graph and the handshaking lemma becomes a free audit: every cable end must land somewhere, so the sum of all connector-side counts has to come out even and equal twice the cable count. When it doesn't, the spreadsheet is lying about at least one cable, and you find out at your desk instead of behind the rack with a flashlight.

The dependency slide at the design review. Software modules, CSCI interfaces, or subsystem data flows drawn as boxes and arrows — that is a directed graph, and the questions the board asks are graph questions. "What breaks if this box dies" is reachability. "Why does the build take forever" is often a cycle. The team that maintains the model as an actual graph answers in seconds; the team that maintains it as a drawing argues from memory.

The comms topology trade. Full mesh between n radios needs n·(n−1)/2 links — 10 nodes is 45 links, 100 nodes is 4,950. A star needs n − 1 links and one hub with degree n − 1 that takes the whole network down with it. That trade — link count against single-point-of-failure degree — is the first graph-theory decision most RF and network engineers make without calling it one.

How it works (the real substance — behavior, gotchas, limits of validity, the mistake people make)

The power of the model is what it deletes. A graph does not know where its vertices sit, how long its edges are, or what the drawing looks like. Two schematics that look nothing alike can be the same graph — same vertices, same connections — and every electrical property follows the graph, not the artwork. That is why a board respin that moves every component but changes no nets requires no new circuit analysis. The flip side: the graph knows nothing you didn't encode. Hop count is not distance, and adjacency is not signal integrity. If cable length, line loss, or delay matters, you must attach weights to the edges; the bare graph will happily report a two-hop path that is electrically worse than a five-hop one.

Get the graph flavor right before writing anything down. Undirected edges for cables and pipes that carry flow both ways; directed edges for signal flow, data dependencies, and check valves. Parallel redundant links make it a multigraph — and note that the adjacency matrix as defined above can't represent them, since a 0-or-1 cell can't count two cables. Model a bidirectional bus as directed and half your reachability answers come out wrong.

The representation choice is a real engineering decision, not a style preference. An adjacency matrix on 10,000 vertices is 10⁸ cells — about 100 MB at a byte per cell — almost all of them zero, because real networks are sparse. The same network at an average degree of 4 is an adjacency list of roughly 10,000 + 40,000 entries. The matrix earns its keep in two places: constant-time "are these two connected" lookups on dense graphs, and the algebra. Take a triangle: A² has 2 on every diagonal entry (out to either neighbor and back) and 1 off the diagonal; trace(A³)/6 counts triangles, and for the triangle itself that's 6/6 = 1. Check.

The classic misread of that algebra: (A^k)[i][j] counts walks, not paths. Walks revisit vertices freely. On a plain 4-node ring, (A³)[0][1] = 4, but only one of those four — around the long way — is a simple path; the other three ping-pong. Anyone using matrix powers to enumerate "distinct routes" through a network is quietly counting echoes.

And the degree parity result is sharper than it looks. Odd-degree vertices come in pairs, always — so a cable plant, a pipe network, or a PCB net class with an odd number of odd-degree nodes is not unusual, it is impossible, and the database describing one contains an error. Cheapest integrity check in the business.

History (who derived it and when, told as a short story with inline [n] citations)

The field has a birthday. The city of Königsberg had four land masses joined by seven bridges, and its citizens had a standing puzzle: walk the town crossing each bridge exactly once. Leonhard Euler presented his answer to the St. Petersburg Academy on 26 August 1735 and published it in 1736 as Solutio problematis ad geometriam situs pertinentis ^[1]^[2]. His move was the founding act of the subject: he threw away the map. Each land mass became a point, each bridge a connection, and the puzzle became a counting argument — every pass through a node uses two bridge-ends, so a node you neither start nor finish at needs even degree. Königsberg's four nodes had degrees 5, 3, 3, and 3, all odd; the walk cannot exist ^[1]. (Note the checksum: 5+3+3+3 = 14 = 2·7 bridges.) Euler stated that even degree throughout was also enough for a round trip; the proof of that half waited until Carl Hierholzer, whose argument was published posthumously in 1873 ^[1]^[3].

The subject then grew up inside engineering and chemistry, not pure mathematics. In 1847 Gustav Kirchhoff analyzed electrical networks by way of their spanning trees, counting independent loops to get exactly the equations a circuit needs and no more — the machinery behind his circuit laws and the matrix-tree theorem that still carries his name ^[4]^[5]. Arthur Cayley named the "tree" in an 1857 paper on analytical forms, apparently unaware of Kirchhoff's work ^[5]^[6], and by 1874 was using trees to count the isomers of the alkanes CₙH₂ₙ₊₂ — pure hydrocarbon bookkeeping ^[7]^[6]. The word "graph" itself came from that same chemistry connection: J. J. Sylvester coined it in an 1878 Nature article, borrowing the look of the chemists' molecular diagrams for his algebra ^[8]^[9]. The scattered results finally became a discipline when Dénes Kőnig published the first textbook, Theorie der endlichen und unendlichen Graphen, in 1936 ^[9]^[10]. Two centuries from a walking puzzle to a field — and the whole time, the working examples were circuits, molecules, and networks. Engineers were the customer from day one.

Related tools (bullet list of HE calculator slugs that use or neighbor this topic, as /tools/ links; omit section if none fit)

/tools/parallel-resistors — resistor network reduction is graph simplification: merging edges between the same two nodes
/tools/voltage-divider — the two-node, two-edge graph every circuit analysis course starts with
/tools/wire-voltage-drop — the edge weight you attach when hop count stops being enough
/tools/pipe-pressure-drop — pipe networks are weighted graphs; loop-balancing methods run on the same node/branch structure as circuit analysis
/tools/link-budget — each edge in a comms topology carries one of these

Sources

Written by HE in our own words from the cited sources — engineering judgment included, your stamp still required. All entries →