Incidence matrix: Question bank — Coding deep dive

Quick vocabulary refresher so every symbol below is already defined before it is used:

vertex = a dot; edge = a line joining two dots; incident = "vertex touches edge".
Indexing scheme: we number the vertices $v_{1}, v_{2}, \dots, v_{n}$ (so the index $i$ runs $1 \dots n$ ) and the edges $e_{1}, e_{2}, \dots, e_{m}$ (so the index $j$ runs $1 \dots m$ ). "Row $i$ " always means the row of vertex $v_{i}$ ; "column $j$ " always means the column of edge $e_{j}$ .
$B$ = the incidence matrix, size $n \times m$ (rows = the $n$ vertices, columns = the $m$ edges); $B_{ij}$ is the entry in row $i$ , column $j$ .
degree $de g (v)$ = how many edge-ends stick into vertex $v$ (see Degree of a vertex).
Directed convention: tail $= - 1$ (edge leaves the vertex), head $= + 1$ (edge enters the vertex).
Self-loop convention (undirected): an edge from a vertex to itself touches that vertex with both its ends, so it adds $2$ to the degree. To keep the rule "row sum $=$ degree" true, we write the entry == $2$ == (not $1$ ) in that vertex's row for a loop column.
All-ones vector $1$ = a column of $n$ ones, one entry per vertex; $1^{T} B$ (the row $1^{T}$ times $B$ ) simply adds up each column of $B$ , giving one number per edge.

Look at the concrete picture below — a tiny triangle graph and its incidence matrix — before diving into the traps, so every phrase ("column of two $1$ 's", "row sum", "column sum $= 0$ ") has a mental image behind it.

True or false — justify

A column of an undirected incidence matrix can be entirely zero.

False. Every edge has two endpoints, so its column always carries two

1

's (or a single

2

for a loop). An all-zero column would mean an edge attached to nothing, which is not an edge.

A row of an incidence matrix can be entirely zero.

True. An isolated vertex (degree

0

) touches no edge, so its row is all zeros. Rows describe vertices, and a lonely vertex is perfectly legal.

B

is square then the graph must be a triangle.

False.

B

is square only when

n = m

(vertices count equals edge count). A triangle (

n = m = 3

) is one such case, but any graph with equally many vertices and edges (e.g. a single cycle of any length) also gives a square

B

In an undirected graph, adding one edge always adds exactly two

1

's to the matrix.

True for a normal edge, false for a loop. A normal edge appends a column with two

1

's; a self-loop appends a column holding a single

2

, adding only one non-zero entry.

Every column of a directed incidence matrix sums to

0

True — with no exceptions. A normal edge has one tail (

- 1

) and one head (

+ 1

) in different rows, and they cancel. A directed self-loop puts both the

- 1

and the

+ 1

in the same row, giving

- 1 + 1 = 0

there too, so the column still sums to

0

Two different graphs can never share the same incidence matrix.

False, subtly. They can differ only by relabelling rows/columns (renaming vertices or reordering edges) and still be the "same" graph up to isomorphism. Beyond relabelling,

B

does pin down the graph structure.

The incidence matrix of a graph with no edges is empty of numbers.

True. With

m = 0

there are zero columns, so

B

is an

n \times 0

matrix — it has rows (the vertices) but nothing to fill in. Every vertex is isolated.

Swapping two columns of

B

changes the graph.

False. Columns are just edge labels; reordering them renames

e_{1}, e_{2}, \dots

but the same vertex-pairs are still connected. The graph is unchanged.

For an undirected graph,

1^{T} B = 0

(the all-ones row times

B

is zero).

False — that is the directed identity, where

+ 1

and

- 1

cancel per column. Undirected columns are

1 + 1 = 2

, so

1^{T} B

gives the all-

2

's row (a

2

per edge), not zero.

Two parallel edges (two edges joining the same pair of vertices) can both appear in one incidence matrix.

True. Each edge is its own column, so parallel edges simply become two identical columns. The incidence matrix handles multigraphs naturally — it just repeats the column.

Spot the error

"A student writes a column with three

1

's, saying vertex

A

B

C

all share edge

e_{3}

." — where's the flaw?

An edge has exactly two endpoints, so at most two

1

's per column. What they described is a hyperedge, not an ordinary graph edge; ordinary incidence matrices can't hold it.

"Since the adjacency matrix is

n \times n

, the incidence matrix is

n \times n

too." — where's the flaw?

Incidence relates two different sets (vertices and edges), so its size is

n \times m

. The adjacency matrix relates vertices to vertices, which is why it is square; the analogy does not carry over.

"In a directed graph I'll use

1

for connected and

0

otherwise, just like undirected." — where's the flaw?

That throws away direction. Without

- 1

+ 1

signs you can't tell tail from head, column sums won't vanish, and the Laplacian identity

L = B B^{T}

fails (

L

is the matrix whose diagonal is the degrees and whose off-diagonal

- 1

's mark adjacent vertices — see Graph Laplacian).

"Two parallel edges must be merged into one column since they connect the same pair." — where's the flaw?

No — each edge is a distinct object and earns its own column, even if it duplicates another. Merging them would lose an edge and mis-count the degree (parallel edges add to degree twice).

"A self-loop should be marked with a single

1

so the column looks normal." — where's the flaw?

A loop attaches to its vertex with both ends, contributing

2

to the degree. Marking

1

would break the rule "row sum

= de g (v)

"; the correct undirected entry is

2

"Row sum equals the number of edges in the whole graph." — where's the flaw?

Row

i

sums only the edges touching vertex

v_{i}

, giving

de g (v_{i})

, not the total edge count

m

. Summing all rows gives

2 m

, which is a different statement (the Handshake Lemma).

"An oriented edge's tail is

+ 1

because the arrow starts positive." — where's the flaw?

Convention is the opposite: tail

= - 1

(edge leaves), head

= + 1

(edge enters). The signs are chosen so each column sums to

0

; swapping them would still cancel but violates the standard used to build the Laplacian Graph Laplacian.

Why questions

Why is the incidence matrix

n \times m

and not

n \times n

Because it describes vertex-to-edge relationships, not vertex-to-vertex. Edges are the objects being catalogued, so each edge earns its own column — giving

m

columns for

n

rows.

Why does summing row

i

give the degree of vertex

v_{i}

Row

i

has a

1

exactly in the columns of edges touching

v_{i}

. Counting those $1$ 's is literally counting $v_{i}$ 's edges, which is the definition of degree.

Why do directed column sums vanish while undirected ones don't?

A directed edge splits its two ends into

- 1

(out) and

+ 1

(in), which cancel. Undirected edges carry two identical

+ 1

's, so they add to

2

with nothing to cancel against.

Why does the incidence matrix "prove" the Handshake Lemma?

Count the

1

's two ways: by columns gives

2

per edge

= 2 m

; by rows gives

\sum_{i = 1}^{n} de g (v_{i})

. The same marks counted two ways must agree, so

\sum de g = 2 m

(see Handshake Lemma).

Why is the oriented incidence matrix preferred for building

L = B B^{T}

The signed entries make

B B^{T}

produce degrees on the diagonal and

- 1

for adjacent pairs — exactly the Laplacian (the

n \times n

matrix that encodes both degree and connectivity, used all over spectral graph theory — see Graph Laplacian). Unsigned entries would give the wrong off-diagonal signs and destroy the identity.

Why can incidence lists beat the full matrix for huge graphs?

Most large graphs are sparse (few edges per vertex), so the matrix is mostly zeros. Storing only the two endpoints per edge — a compact "edge list", the idea behind Sparse graph representations — saves the wasted space of all those

0

's that the full

n \times m

grid would hold.

Edge cases

What does the incidence matrix look like for a single isolated vertex (no edges)?

1 \times 0

matrix: one row, zero columns. The vertex exists but has nothing to be incident with, so its degree is

0

What is the incidence matrix of the empty graph with no vertices and no edges (

n = 0, m = 0

0 \times 0

matrix — no rows and no columns at all. It is the degenerate base case: nothing to index, every sum is an empty sum equal to

0

, and

2 m = 0

still holds trivially.

How does a directed self-loop appear, and does its column still sum to

0

Both the tail (

- 1

) and head (

+ 1

) land in the same row (the loop's single vertex), so that row shows

- 1 + 1

. The column still sums to

0

— the identity has no exception; the only quirk is that the two signs share one row instead of two.

How do two parallel edges show up in the matrix?

As two identical columns (same pair of rows carrying the two

1

's). The matrix stores multigraphs faithfully; each parallel edge independently adds

1

to each endpoint's degree.

For a graph that is just two vertices joined by a single edge, what are the row and column sums?

Each row sums to $1$ (each vertex has degree

1

) and the single column sums to $2$ (its two endpoints). This is the smallest non-trivial incidence matrix.

What is the total number of

1

's in a loop-free undirected graph with

m

edges, regardless of

n

Always

2 m

— two per column, independent of how many vertices exist. This equals

\sum_{i} de g (v_{i})

, recovering the Handshake Lemma.

If every vertex in an undirected graph has even degree, what can you say about its rows?

Every row sums to an even number. Since a row sum is the degree, "all degrees even" translates directly into "all row sums even" — useful for detecting Eulerian structure.

What happens to

B

if you delete an edge?

You delete its column;

m

drops by one and the two endpoints each lose

1

from their degree (row sum). No other entry changes, showing edges are independent columns.

Connections

Incidence matrix — the parent note these traps drill.
Adjacency matrix — the $n \times n$ representation confused with $B$ in several traps.
Graph Laplacian — where the directed sign convention pays off ( $L = B B^{T}$ ).
Degree of a vertex — the row-sum quantity.
Handshake Lemma — the count-two-ways result.
Sparse graph representations — why the full matrix is often avoided.

Question bank — Incidence matrix