Incidence matrix: Exercises — Coding deep dive

Level 1 — Recognition

(Can you read a single cell and a single row/column correctly?)

L1.1 In an undirected incidence matrix $B$ , what does the entry $B_{ij} = 1$ literally tell you about vertex $v_{i}$ and edge $e_{j}$ ?

Recall Solution

It says ==vertex $v_{i}$ is an endpoint of edge $e_{j}$ == — the dot $v_{i}$ is one of the two ends of the line $e_{j}$ . If $B_{ij} = 0$ , the line $e_{j}$ does not touch the dot $v_{i}$ at all.

L1.2 A graph has $n = 5$ vertices and $m = 7$ edges. What is the shape (rows × columns) of its incidence matrix?

Recall Solution

Rows = vertices, columns = edges, so the matrix is $5 \times 7$ . Not $5 \times 5$ — that would be the Adjacency matrix. Edges are the things being described, so they get one column each.

L1.3 Here is one column of an undirected incidence matrix (the whole column for edge $e_{2}$ ): $0101$ Which two vertices does edge $e_{2}$ join?

Recall Solution

The $1$ 's sit in rows $2$ and $4$ , so $e_{2} = (v_{2}, v_{4})$ . A column is an edge written vertically: the two $1$ 's are literally its two endpoints.

Level 2 — Application

(Build small matrices; use the row-sum = degree and column rules.)

L2.1 Build the undirected incidence matrix for a path $1 - 2 - 3 - 4$ with edges $e_{1} = (1, 2), e_{2} = (2, 3), e_{3} = (3, 4)$ .

Recall Solution

Scan each edge, mark its two endpoints:

	$e_{1}$	$e_{2}$	$e_{3}$
$1$	1	0	0
$2$	1	1	0
$3$	0	1	1
$4$	0	0	1

Check: row sums are $1, 2, 2, 1$ → degrees $de g (1) = 1, de g (2) = 2, de g (3) = 2, de g (4) = 1$ . The two endpoints of a path have degree $1$ , the two middle vertices degree $2$ . ✔ See the picture:

L2.2 Using the matrix from L2.1, compute the sum of all entries. What graph fact does it equal?

Recall Solution

Sum $= 1 + 2 + 2 + 1 = 6$ . There are $m = 3$ edges, two $1$ 's per column, so the total is $2 m = 6$ . This is the Handshake Lemma: $\sum_{i} de g (v_{i}) = 2 m$ . Counting the marks by columns ( $2 m$ ) and by rows ( $\sum de g$ ) must agree.

L2.3 Build the directed incidence matrix for the arrows $e_{1} : 1 \to 2, e_{2} : 3 \to 2, e_{3} : 1 \to 3$ .

Recall Solution

Tail $= - 1$ , head $= + 1$ :

	$e_{1}$	$e_{2}$	$e_{3}$
$1$	$- 1$	$0$	$- 1$
$2$	$+ 1$	$+ 1$	$0$
$3$	$0$	$- 1$	$+ 1$

Check every column sums to $0$ : $(- 1) + (+ 1) = 0$ for each. ✔ Vertex $1$ has two tails leaving it (two $- 1$ 's); vertex $2$ has two heads entering it (two $+ 1$ 's).

Level 3 — Analysis

(Reverse-engineer, spot contradictions, handle degenerate cases.)

L3.1 An undirected incidence matrix has a column with three $1$ 's. What is wrong?

Recall Solution

An edge is a line, and a line has exactly two endpoints. Three $1$ 's would mean one edge touches three vertices, which is impossible for an ordinary graph. Either the matrix is wrong, or you have drawn a hyperedge (a different object, not a simple graph). Valid columns have exactly two $1$ 's — or a single " $2$ " for a self-loop.

L3.2 You are handed this undirected matrix. Draw the graph and give all degrees. $B = 1100101001100101$

Recall Solution

Read each column as an edge (rows of its two $1$ 's):

$e_{1}$ : rows $1, 2 \Rightarrow (1, 2)$
$e_{2}$ : rows $1, 3 \Rightarrow (1, 3)$
$e_{3}$ : rows $2, 3 \Rightarrow (2, 3)$
$e_{4}$ : rows $2, 4 \Rightarrow (2, 4)$

So vertices $1, 2, 3$ form a triangle, and vertex $4$ hangs off vertex $2$ . Row sums (degrees): $de g (1) = 2, de g (2) = 3, de g (3) = 2, de g (4) = 1$ . Sanity: $\sum de g = 2 + 3 + 2 + 1 = 8 = 2 m = 2 (4)$ . ✔ Picture:

L3.3 A single edge is a self-loop at vertex $1$ (edge $1 \to 1$ ). Write the undirected column, and explain the entry.

Recall Solution

The column is a single $2$ in row $1$ (all other rows $0$ ). A loop meets vertex $1$ with both of its ends, so it contributes $2$ to the degree — the " $2$ " keeps the row sum = degree rule intact. This is the one exception to "exactly two $1$ 's per column"; the two marks fuse into one entry of $2$ .

Level 4 — Synthesis

(Combine incidence with degree, Handshake, and the Laplacian.)

L4.1 A connected undirected graph has $n = 6$ vertices and every vertex has degree $3$ . How many edges does it have, and how many $1$ 's appear in its incidence matrix?

Recall Solution

By Handshake, $\sum de g = 2 m$ . Here $\sum de g = 6 \times 3 = 18$ , so $m = 18/2 = 9$ edges. Number of $1$ 's $= 2 m = 18$ (two per column). Note $18$ equals both counts — that equality is the Handshake Lemma.

L4.2 For the directed graph of L2.3, compute $L = B B^{T}$ and confirm each row of $L$ sums to $0$ .

Recall Solution

With $B = - 1 10 01 - 1 - 1 01,$ the entry $(B B^{T})_{ii}$ counts edges at $v_{i}$ (its degree), and $(B B^{T})_{ij}$ for $i \neq = j$ is $- (edges between i, j)$ : $L = B B^{T} = 2 - 1 - 1 - 1 2 - 1 - 1 - 1 2 .$ Every row sums to $2 - 1 - 1 = 0$ . Why $0$ ? Because $1^{T} B = 0$ (columns of $B$ sum to $0$ ), so $L 1 = B (B^{T} 1) = 0$ . This is the defining property of the Graph Laplacian.

L4.3 True or false: In an undirected incidence matrix, the number of $1$ 's in row $i$ equals the number of columns whose top-most $1$ is in row $i$ . Explain.

Recall Solution

False. The number of $1$ 's in row $i$ is $de g (v_{i})$ — it counts every edge touching $v_{i}$ , whether $v_{i}$ is the "top" endpoint or the "lower" one. The "top-most $1$ " idea would only count edges where $v_{i}$ is the smaller-indexed endpoint, undercounting. Degree does not care about ordering of endpoints.

Level 5 — Mastery

(Full round-trip: graph → matrix → recovered structure, all cases.)

L5.1 A graph on vertices ${1, 2, 3}$ has: one edge $(1, 2)$ , one edge $(2, 3)$ , and a self-loop at $3$ . Build the full undirected incidence matrix, list all degrees, and verify Handshake carefully (loops count once as an edge but $2$ toward degree).

Recall Solution

Columns: $e_{1} = (1, 2), e_{2} = (2, 3), e_{3} = loop at 3$ .

	$e_{1}$	$e_{2}$	$e_{3}$
$1$	1	0	0
$2$	1	1	0
$3$	0	1	2

Row sums (degrees): $de g (1) = 1, de g (2) = 2, de g (3) = 1 + 2 = 3$ . So $\sum de g = 1 + 2 + 3 = 6$ . Edges: $m = 3$ . Handshake with loops: each loop adds $2$ to $\sum de g$ and counts as one edge, so $\sum de g = 2 m$ still holds: $2 \times 3 = 6$ . ✔ Picture:

L5.2 You receive only this directed incidence matrix. Reconstruct every arrow, then compute the out-degree (number of tails, i.e. $- 1$ 's) of each vertex. $B = - 1 10 - 1 01 0 - 1 1$

Recall Solution

Column $e_{j}$ : the row with $- 1$ is the tail (start), the row with $+ 1$ is the head (end).

$e_{1}$ : $- 1$ in row $1$ , $+ 1$ in row $2 \Rightarrow 1 \to 2$
$e_{2}$ : $- 1$ in row $1$ , $+ 1$ in row $3 \Rightarrow 1 \to 3$
$e_{3}$ : $- 1$ in row $2$ , $+ 1$ in row $3 \Rightarrow 2 \to 3$

Out-degrees (count $- 1$ 's per row): vertex $1$ has two $- 1$ 's $\Rightarrow 2$ ; vertex $2$ has one $\Rightarrow 1$ ; vertex $3$ has none $\Rightarrow 0$ . Cross-check: total out-degree $= 2 + 1 + 0 = 3 = m$ edges — every edge has exactly one tail. ✔

L5.3 For any oriented graph, prove in one line why $1^{T} B = 0$ (the all-ones row vector times $B$ gives all zeros), and state the one edge type that would break it.

Recall Solution

$(1^{T} B)_{j} = \sum_{i} B_{ij} = (- 1) + (+ 1) = 0$ for each non-loop column, because every directed edge has exactly one tail and one head. So $1^{T} B = 0$ . Breaker: a directed self-loop — its tail and head are the same vertex, so people often write $0$ (they cancel in the same row) rather than two separate signs, and the column has no $\pm 1$ pair to speak of. Oriented Laplacians therefore usually assume no self-loops.

Connections

Degree of a vertex — every L2/L5 degree is a row sum of $B$ .
Handshake Lemma — the engine behind L2.2, L4.1, L5.1.
Graph Laplacian — assembled in L4.2 as $L = B B^{T}$ .
Adjacency matrix — the $n \times n$ contrast raised in L1.2.
Sparse graph representations — how these matrices are stored when $n, m$ are large.