The Incidence Matrix

Graph Theory · Axiom Academy

An alternative matrix representation capturing vertex-edge relationships 1. Definition: Rows and Columns The incidence matrix B of a graph G with n vertices and m edges is an n×m matrix where: Each row corresponds to a vertex Each column corresponds to an edge B[v,e] = 1 if vertex v is incident to edge e For an undirected graph, each edge column has exactly two 1s (one for each endpoint). This reflects that each edge connects exactly two vertices. 3. Directed Graphs: Signed Incidence For directed graphs , we use signed entries to indicate direction: B[v,e] = +1 if v is the tail (source) of edge e B[v,e] = -1 if v is the head (target) of edge e B[v,e] = 0 if v is not incident to e 4. Relationship to Adjacency Matrix For simple graphs (no loops or multiple edges), there's a beautiful relationship between the incidence matrix B and the adjacency matrix A: This means we can derive the adjacency matrix from the incidence matrix! 5. Applications in Network Flow and Circuits The incidence matrix is particularly powerful in applications where edges carry flow or current:

This is the written version of the interactive lesson above. See the full Graph Theory course.