Encyclopedia

Edge and vertex spaces

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated June 21, 2026

In the mathematical discipline of graph theory, the edge space and vertex space of an undirected graph are vector spaces defined in terms of the edge and vertex sets, respectively. These vector spaces make it possible to use techniques of linear algebra in studying the graph.

01Definition

Let $G:=(V,E)$ be a finite undirected graph. The vertex space ${\mathcal {V}}(G)$ of G is the vector space over the finite field of two elements $\mathbb {Z} /2\mathbb {Z} :=\lbrace 0,1\rbrace$ of all functions $V\rightarrow \mathbb {Z} /2\mathbb {Z}$ . Every element of ${\mathcal {V}}(G)$ naturally corresponds the subset of V which assigns a 1 to its vertices. Also every subset of V is uniquely represented in ${\mathcal {V}}(G)$ by its characteristic function. The edge space ${\mathcal {E}}(G)$ is the $\mathbb {Z} /2\mathbb {Z}$ -vector space freely generated by the edge set E. The dimension of the vertex space is thus the number of vertices of the graph, while the dimension of the edge space is the number of edges.

These definitions can be made more explicit. For example, we can describe the edge space as follows:

elements are subsets of $E$ , that is, as a set ${\mathcal {E}}(G)$ is the power set of E
vector addition is defined as the symmetric difference: $P+Q:=P\triangle Q\qquad P,Q\in {\mathcal {E}}(G)$
scalar multiplication is defined by:
- $0\cdot P:=\emptyset \qquad P\in {\mathcal {E}}(G)$
- $1\cdot P:=P\qquad P\in {\mathcal {E}}(G)$

The singleton subsets of E form a basis for ${\mathcal {E}}(G)$ .

One can also think of ${\mathcal {V}}(G)$ as the power set of V made into a vector space with similar vector addition and scalar multiplication as defined for ${\mathcal {E}}(G)$ .

02Properties

The incidence matrix $H$ for a graph $G$ defines one possible linear transformation

$H:{\mathcal {E}}(G)\to {\mathcal {V}}(G)$

between the edge space and the vertex space of $G$ . The incidence matrix of $G$ , as a linear transformation, maps each edge to its two incident vertices. Let $vu$ be the edge between $v$ and $u$ then

$H(vu)=v+u$

The cycle space and the cut space are subspaces of the edge space.

Watch videos about Edge and vertex spacesExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Edge and vertex spaces”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Images, from Wikimedia Commons:

Vertex space for 3 vertex graphs.svg by BagLuke, CC0

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Edge and vertex spaces

01Definition

02Properties

Sources and credits

Related topics

Cycle space

Cut (graph theory)