Edge and vertex spaces

<h2 id="definition">Definition</h2>
Let 
 
 
 
 G
 :=
 (
 V
 ,
 E
 )
 
 
 {\displaystyle G:=(V,E)}
 
 be a finite undirected graph. The vertex space 
 
 
 
 
 
 V
 
 
 (
 G
 )
 
 
 {\displaystyle {\mathcal {V}}(G)}
 
 of G is the vector space over the <a href="/facts/Finite_field/UkMGJo3m">finite field</a> of two elements

Z
 
 
 /
 
 2
 
 Z
 
 :=
 {
 0
 ,
 1
 }
 
 
 {\displaystyle \mathbb {Z} /2\mathbb {Z} :=\lbrace 0,1\rbrace }
 
 of all functions 
 
 
 
 V
 →
 
 Z
 
 
 /
 
 2
 
 Z
 
 
 
 {\displaystyle V\rightarrow \mathbb {Z} /2\mathbb {Z} }
 
. Every element of 
 
 
 
 
 
 V
 
 
 (
 G
 )
 
 
 {\displaystyle {\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 
 
 
 
 
 
 V
 
 
 (
 G
 )
 
 
 {\displaystyle {\mathcal {V}}(G)}
 
 by its characteristic function. The edge space 
 
 
 
 
 
 E
 
 
 (
 G
 )
 
 
 {\displaystyle {\mathcal {E}}(G)}
 
 is the 
 
 
 
 
 Z
 
 
 /
 
 2
 
 Z
 
 
 
 {\displaystyle \mathbb {Z} /2\mathbb {Z} }
 
-vector space freely generated by the edge set E. The <a href="/facts/Dimension_(vector_space)/z8m02A3W">dimension</a> 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:

<ul><li>elements are subsets of 
 
 
 
 E
 
 
 {\displaystyle E}
 
, that is, as a set 
 
 
 
 
 
 E
 
 
 (
 G
 )
 
 
 {\displaystyle {\mathcal {E}}(G)}
 
 is the <a href="/facts/Power_set/FVuf8PDD">power set</a> of E</li>
<li><a href="/facts/Vector_addition/bCLrdksy">vector addition</a> is defined as the <a href="/facts/Symmetric_difference/W2QST1Qr">symmetric difference</a>: 
 
 
 
 P
 +
 Q
 :=
 P
 △
 Q
 
 P
 ,
 Q
 ∈
 
 
 E
 
 
 (
 G
 )
 
 
 {\displaystyle P+Q:=P\triangle Q\qquad P,Q\in {\mathcal {E}}(G)}
 
</li>
<li><a href="/facts/Scalar_multiplication/jroFDfbM">scalar multiplication</a> is defined by:
<ul><li>
 
 
 
 0
 ⋅
 P
 :=
 ∅
 
 P
 ∈
 
 
 E
 
 
 (
 G
 )
 
 
 {\displaystyle 0\cdot P:=\emptyset \qquad P\in {\mathcal {E}}(G)}
 
</li>
<li>
 
 
 
 1
 ⋅
 P
 :=
 P
 
 P
 ∈
 
 
 E
 
 
 (
 G
 )
 
 
 {\displaystyle 1\cdot P:=P\qquad P\in {\mathcal {E}}(G)}
 
</li></ul></li></ul>
The <a href="/facts/Singleton_(mathematics)/LtNVfujT">singleton</a> subsets of E form a <a href="/facts/Basis_(linear_algebra)/89IPoN6c">basis</a> for 
 
 
 
 
 
 E
 
 
 (
 G
 )
 
 
 {\displaystyle {\mathcal {E}}(G)}
 
.
One can also think of 
 
 
 
 
 
 V
 
 
 (
 G
 )
 
 
 {\displaystyle {\mathcal {V}}(G)}
 
 as the power set of V made into a vector space with similar vector addition and scalar multiplication as defined for 
 
 
 
 
 
 E
 
 
 (
 G
 )
 
 
 {\displaystyle {\mathcal {E}}(G)}
 
.

<h2 id="properties">Properties</h2>
The <a href="/facts/Incidence_matrix/eMXGWQBw">incidence matrix</a> 
 
 
 
 H
 
 
 {\displaystyle H}
 
 for a graph 
 
 
 
 G
 
 
 {\displaystyle G}
 
 defines one possible <a href="/facts/Linear_transformation/Q1PBKNVV">linear transformation</a>

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

between the edge space and the vertex space of 
 
 
 
 G
 
 
 {\displaystyle G}
 
. The incidence matrix of 
 
 
 
 G
 
 
 {\displaystyle G}
 
, as a linear transformation, maps each edge to its two <a href="/facts/Incident_(graph_theory)/kw3eIBUe">incident</a> vertices. Let 
 
 
 
 v
 u
 
 
 {\displaystyle vu}
 
 be the edge between 
 
 
 
 v
 
 
 {\displaystyle v}
 
 and 
 
 
 
 u
 
 
 {\displaystyle u}
 
 then

H
        (
        v
        u
        )
        =
        v
        +
        u
      
    
    {\displaystyle H(vu)=v+u}

The <a href="/facts/Cycle_space/NeWx2guT">cycle space</a> and the <a href="/facts/Cut_space/1lKf2IIW">cut space</a> are <a href="/facts/Linear_subspace/2wtKTgHL">subspaces</a> of the edge space.

<ul><li>Diestel, Reinhard (2005), <a href="http://diestel-graph-theory.com/">Graph Theory</a> (3rd ed.), <a href="/facts/Springer_Science%2BBusiness_Media/nAesf6nT">Springer</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 3-540-26182-6 (the electronic 3rd edition is freely available on author's site).</li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Cycle_space/NeWx2guT">Cycle space</a></li>
<li><a href="/facts/Cut_space/1lKf2IIW">Cut space</a></li></ul>

Edge and vertex spaces open-in-new

Edge and vertex spaces