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.

Definition

be a finite undirected graph. The vertex space of G is the vector space over the finite field naturally corresponds the subset of V which assigns a 1 to its vertices. Also every subset of V by its characteristic function. The edge space-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:

• is the power set of E

• vector addition is defined as the symmetric difference

scalar multiplication is defined by:

The singleton subsets of E form a basis.

as the power set of V.

Properties

The incidence matrix defines one possible linear transformation

, as a linear transformation, maps each edge to its two incident then

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

References

• (the electronic 3rd edition is freely available on author's site).

See also

• Cycle space

• Cut space