Worked examples — Incidence matrix

Before anything, let us pin down our one central symbol and re-earn one word we lean on constantly.

---

The scenario matrix

Every incidence-matrix problem falls into one of these case classes. We will hit each cell with at least one worked example.

#	Case class	The twist it tests	Worked in
C1	Undirected, simple	The plain "1 if endpoint" rule	Example 1
C2	Directed, simple	Signs $-1$ (tail) / $+1$ (head), columns sum to 0	Example 2
C3	Undirected self-loop	An edge whose two endpoints are the same vertex → entry "2"	Example 3
C4	Directed self-loop	A loop in a digraph: a $-1$ and a $+1$ in the same row	Example 4
C5	Parallel (multi) edges	Two edges joining the same pair	Example 5
C6	Isolated vertex (degree 0)	A dot touching no edge → an all-zero row	Example 6
C7	Degenerate: no edges at all	$m=0$, matrix has zero columns	Example 6
C8	Read backwards	Given the matrix, recover the graph	Example 7
C9	Word problem (real world)	Translate a story into $B$	Example 8
C10	Exam twist: prove with $B$	Use $B$ to prove Handshake / column-rank facts	Example 9
C11	Limiting behaviour	What $B$ looks like as the graph gets dense/sparse	Example 10

---

Example 1 — Undirected, simple (cell C1)

Forecast: Guess before reading — how many $1$'s total will the matrix have, and what will the degree of vertex 2 be?

Steps.

1. List rows and columns. Rows $=\{1,2,3,4\}$ (the 4 dots), columns $=\{e_1,e_2,e_3\}$ (the 3 lines). So $B$ is $4\times 3$. Why this step? The matrix is ==$n\times m$==: 4 vertices, 3 edges. Fixing the shape first stops the "square matrix" mistake.
2. Fill each column by its two endpoints. $e_1$ touches $1,2$; $e_2$ touches $2,3$; $e_3$ touches $3,4$. Why this step? An edge has exactly two endpoints, so each column gets exactly two $1$'s.

$B=\begin{array}{cccc}& e_1& e_2& e_3\\ 1& 1& 0& 0\\ 2& 1& 1& 0\\ 3& 0& 1& 1\\ 4& 0& 0& 1\end{array}$

3. Read degrees off row sums. Row 1: $1$; row 2: $2$; row 3: $2$; row 4: $1$. Why this step? The row sum ${\sum }_j{B}_{ij}=\mathrm{deg}(v_i)$ — counting the marks in a row is counting the edges at that vertex.

The figure below draws this path with each edge coloured and each vertex labelled by its degree — look at how the two end vertices carry a single blue edge (degree 1) while the two middle ones sit between two edges (degree 2), exactly the row sums we just computed.

Verify: Total $1$'s $=2m=2\cdot 3=6$. Adding row sums: $1+2+2+1=6$ ✔. The two "end" vertices (1,4) have degree 1, the two "middle" ones degree 2 — exactly what a path looks like.

---

Example 2 — Directed, simple (cell C2)

Forecast: In the undirected version every column summed to 2. What will each column sum to now?

Steps.

1. Same shape, signed entries. For each edge, put $-1$ at its tail (where the arrow leaves) and $+1$ at its head (where the arrow enters). Why this step? Direction is information; a bare $1$ throws it away. The sign convention ==tail $=-1$, head $=+1$== is what preserves it.

$B=\begin{array}{cccc}& e_1& e_2& e_3\\ 1& -1& 0& 0\\ 2& +1& -1& 0\\ 3& 0& +1& -1\\ 4& 0& 0& +1\end{array}$

2. Sum each column. $e_1:-1+1=0$; $e_2:-1+1=0$; $e_3:-1+1=0$. Why this step? Each edge has exactly one tail and one head, so its column contains one $-1$ and one $+1$ — they cancel.

In the figure below, every edge is now an arrow; the pink $-1$ sits at each arrow's tail and the yellow $+1$ at its head. Trace any single arrow and you see the two signs that cancel to give that column's zero sum.

Verify: Every column sums to $0$, so $1^{T}B=0$. This is precisely the property that makes the Graph Laplacian $L=B{B}^T$ well-behaved. Column sums vanishing is the signature that you oriented every edge exactly once. ✔

---

Example 3 — Undirected self-loop (cell C3)

Forecast: A normal column has two $1$'s. A loop only touches ONE vertex — so what does its column look like, and what is $\mathrm{deg}(1)$?

Steps.

1. The loop's column. A loop leaves and returns to the same vertex, so both endpoints are vertex 1. We record that as a single entry $2$ in row 1. Why this step? Writing "2" keeps the promise that row-sum $=$ degree: a loop adds 2 to a vertex's degree (you can leave along it and arrive along it).
2. The normal edge. $e_2$ touches $1$ and $2$ → a $1$ in each. Why this step? $e_2$ is an ordinary edge with two distinct endpoints, so it obeys the plain "two 1's per column" rule from Example 1 — the loop is the special case, not this.

$B=\begin{array}{ccc}& e_1& e_2\\ 1& 2& 1\\ 2& 0& 1\end{array}$

3. Degrees. Row 1: $2+1=3$; row 2: $0+1=1$.

Verify: $\mathrm{deg}(1)=3$ (loop contributes 2, edge $e_2$ contributes 1) and $\mathrm{deg}(2)=1$. Check the Handshake Lemma: $\sum \mathrm{deg}=3+1=4$. Counting edges "with loops weighing 2": loop $=2$, $e_2=2$, total $=4$ ✔. This is the one exception to "every column has exactly two 1's."

---

Example 4 — Directed self-loop (cell C4)

Forecast: In the undirected loop we wrote a single "2". A directed loop has a tail ($-1$) and a head ($+1$) — but both land on vertex 1. What single number goes in that cell, and does its column still sum to 0?

Steps.

1. The directed loop's column. The loop's tail is vertex 1 ($-1$) and its head is also vertex 1 ($+1$). Both contributions fall in the same cell, so we add them: $-1+(+1)=0$. Why this step? Signs are additive within a cell. A directed loop therefore leaves a 0 in row 1 — the tail and head cancel inside one entry because they share a vertex.
2. The ordinary directed edge. $e_2:1\to 2$ gives $-1$ at its tail (row 1) and $+1$ at its head (row 2). Why this step? $e_2$ has two distinct endpoints, so its $-1$ and $+1$ land in different rows — the normal directed rule from Example 2.

$B=\begin{array}{ccc}& e_1& e_2\\ 1& 0& -1\\ 2& 0& +1\end{array}$

3. Column sums. $e_1:0$; $e_2:-1+1=0$. Why this step? We are testing whether the "every column sums to 0" law survives a loop — it does, but for the loop the cancellation happens within a single cell rather than across two rows.

Verify: Both columns sum to $0$, so $1^{T}B=0$ still holds ✔. Note the contrast with Example 3: the undirected loop showed a 2, the directed loop shows a 0. A directed loop is therefore invisible to $B{B}^T$ — a known quirk worth remembering when building the Graph Laplacian.

---

Example 5 — Parallel edges (cell C5)

Forecast: Adjacency matrices merge parallel edges into a count. Does the incidence matrix merge them or keep them separate?

Steps.

1. One column per edge — always. $e_1$ and $e_2$ are different edges, so they get different columns, even though they join the same pair. Why this step? Columns are indexed by edges, not by vertex-pairs. This is exactly why the incidence matrix can represent multigraphs where an adjacency matrix would blur them.

$B=\begin{array}{ccc}& e_1& e_2\\ 1& 1& 1\\ 2& 1& 1\end{array}$

2. Degrees. Row 1: $2$; row 2: $2$. Why this step? Each row sum still equals the degree; both vertices sit on both edges, so each has degree 2 — the row-sum rule doesn't care that the two edges are parallel.

Verify: Total $1$'s $=2m=2\cdot 2=4$; row sums $2+2=4$ ✔. Each of vertices 1 and 2 has degree 2, because two edges leave each. Columns are identical here, which is fine — identical columns simply mean parallel edges.

---

Example 6 — Isolated vertex & the empty graph (cells C6, C7)

Forecast: What does the row for a vertex with no edges look like? And what happens to a matrix that has vertices but no edges?

Steps (a).

1. Fill only the real edge. $e_1$ marks rows 1 and 2. Why this step? We build $B$ purely from edges; with only $e_1$ present, only its two endpoints (1 and 2) receive a mark, and nothing else is touched.
2. Row 3 is all zeros. Vertex 3 is an endpoint of no edge. Why this step? An isolated vertex (degree 0) contributes a row of zeros — the matrix still needs the row so the row-count stays $n=3$.

$B=\begin{array}{cc}& e_1\\ 1& 1\\ 2& 1\\ 3& 0\end{array}$

Verify (a): Row 3 sums to $0=\mathrm{deg}(3)$ ✔. Total $1$'s $=2\cdot 1=2$; row sums $1+1+0=2$ ✔.

Steps (b). With $m=0$ there are no columns. $B$ is a $3\times 0$ matrix — three empty rows. Why this step? Shape is $n\times m=3\times 0$. The degenerate case is not "undefined"; it is a genuine matrix with zero width, and every row sum is the empty sum $=0$, so every degree is $0$. ✔

---

Example 7 — Read the matrix backwards (cell C8)

Forecast: In each column, where is the $-1$ and where is the $+1$? That literally tells you the arrow.

Steps.

1. Column $e_1$: $-1$ in row 1, $+1$ in row 2 → arrow $1\to 2$. Why this step? $-1=$ tail (start), $+1=$ head (end). Reading a column decodes one edge.
2. Column $e_2$: $-1$ in row 2, $+1$ in row 3 → arrow $2\to 3$. Why this step? Same decode applied to the next column — the $-1$ locates the tail, the $+1$ the head, giving the second arrow.
3. Column $e_3$: $-1$ in row 3, $+1$ in row 1 → arrow $3\to 1$. Why this step? Finishing every column guarantees we recover all edges; this last arrow closes the loop back to vertex 1.

So the graph is a directed 3-cycle $1\to 2\to 3\to 1$.

The figure below shows the recovered cycle — follow the blue arrows around the triangle and confirm each matches the tail→head we read out of its column.

Verify: Every column sums to 0 (each has one $-1$, one $+1$) ✔. Row sums: row 1 $=-1+1=0$, row 2 $=+1-1=0$, row 3 $=+1-1=0$ — every vertex has one arrow in and one out, exactly a directed cycle. ✔

---

Example 8 — Word problem (cell C9)

Forecast: "Pays" has a direction — the payer is the tail. Guess Ann's row before building, and whether the group's net signs sum to zero.

Steps.

1. Choose orientation. "$X$ pays $Y$" $\Rightarrow$ arrow $X\to Y$, so $X$ (payer) is tail $=-1$, $Y$ is head $=+1$. Why this step? We must fix a convention first; "money leaves the payer" makes the payer the tail.
2. Rows $=$ people (Ann, Bo, Cy), columns $=$ transactions ($t_1,t_2,t_3$). Why this step? $B$ is always vertices-by-edges; here "people" play the vertex role and "transactions" the edge role, so the shape is $3\times 3$ with people down the side.

$B=\begin{array}{cccc}& t_1& t_2& t_3\\ \text{Ann}& -1& 0& -1\\ \text{Bo}& +1& -1& 0\\ \text{Cy}& 0& +1& +1\end{array}$

3. Interpret row sums as (money in) $-$ (money out). Ann $=-2$ (received $0$, paid twice: $0-2$), Bo $=0$ (received once, paid once: $1-1$), Cy $=+2$ (received twice, paid $0$: $2-0$). Why this step? A directed row sum counts $(+1)$'s for arrows into the vertex (money in) and $(-1)$'s for arrows out (money out), so the row sum is (money in) $-$ (money out) — matching the Forecast's question exactly.

Verify: Total of all row sums $=-2+0+2=0$. This must hold: every transaction contributes one $-1$ and one $+1$, so the grand total is always $0$ ($1^{T}B=0$). Money is conserved across the group ✔.

---

Example 9 — Exam twist: prove Handshake with $B$ (cell C10)

Forecast: The matrix has a fixed number of $1$'s. Can you count them two ways?

Steps.

1. Count all $1$'s by columns. Each of the $m$ columns has exactly two $1$'s (its two endpoints). Total $=2m$. Why this step? The structural fact "two $1$'s per column" is the whole engine.
2. Count all $1$'s by rows. Row $i$ sums to $\mathrm{deg}(v_i)$, so the grand total is ${\sum }_i\mathrm{deg}(v_i)$. Why this step? Row sum $=$ degree, from Example 1.
3. Both count the same marks, so they are equal: ${\sum }_{i=1}^n\mathrm{deg}(v_i)=\underset{\text{by columns}}{\underbrace{2m}}.$

Verify: Reuse Example 1's path: $\sum \mathrm{deg}=1+2+2+1=6$ and $2m=2\cdot 3=6$ ✔. A corollary drops out for free: since $2m$ is even, the number of odd-degree vertices is even.

---

Example 10 — Limiting behaviour: sparse vs dense (cell C11)

Forecast: $B$ always has exactly $2m$ non-zeros (Example 9). As a graph gets dense, does that fraction go up or down?

Steps.

1. $K_4$: $n=4$, $m=\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$. Size $=4\times 6=24$ cells; non-zeros $=2m=12$. Fraction filled $=12/24=0.5$. Why this step? $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=\frac{4\cdot 3}{2}=6$ counts the pairs; each column still has just two $1$'s.
2. Star: $n=4$, $m=3$. Size $=4\times 3=12$ cells; non-zeros $=2m=6$. Fraction $=6/12=0.5$. Why identical? Non-zeros $=2m$ and cells $=n\cdot m$, so fraction $=\frac{2m}{nm}=\frac{2}{n}$ — it depends only on $n$, not on how many edges! For $n=4$ that is $2/4=0.5$ in both.
3. Limit as $n\to \infty$: fraction $=2/n\to 0$. The matrix becomes overwhelmingly zeros. Why this step? Each column has two $1$'s no matter how tall it is, so large graphs give extremely sparse incidence matrices.

The figure below plots the fill fraction $2/n$ against $n$: notice the pink dot at $n=4$ (where $K_4$ and the star agree at $0.5$) and the blue dot far right showing the curve collapsing toward zero — the visual reason large graphs demand sparse storage.

Verify: $K_4$: $2m/(nm)=12/24=0.5$; star: $6/12=0.5$; both equal $2/n=2/4=0.5$ ✔. For $n=1000$, fraction $=2/1000=0.002$ — this is exactly why big graphs are stored with Sparse graph representations instead of dense arrays.

---

Recall Self-test: match example to cell

Which example proved the Handshake Lemma from $B$? ::: Example 9 (cell C10), by double-counting the $1$'s. Which case makes a column contain a single "2" instead of two "1"s? ::: An undirected self-loop (Example 3, cell C3). What does a directed self-loop leave in its cell, and why? ::: A single "0" — the tail $-1$ and head $+1$ share the same vertex and cancel in one cell (Example 4, cell C4). Why does the fill-fraction of an incidence matrix equal $2/n$? ::: Non-zeros $=2m$, cells $=nm$, ratio $=2/n$ — independent of $m$ (Example 10). How do you recover a directed graph from $B$? ::: Read each column: the $-1$ is the tail, the $+1$ is the head (Example 7).

---

---

Connections

• Incidence matrix — the parent note whose rules we stress-tested here.
• Degree of a vertex — every row sum in these examples.
• Handshake Lemma — proved from $B$ in Example 9.
• Adjacency matrix — contrast in Example 5 (it merges parallel edges; $B$ keeps them).
• Graph Laplacian — the vanishing column sums (Examples 2, 4) feed $L=B{B}^T$.
• Sparse graph representations — motivated by the $2/n$ limit in Example 10.

Scenario Map