Graph (topology)

Topological space arising from a usual graph

In topology, a branch of mathematics, a graph is a topological space which arises from a usual graph G = ( E , V ) {\displaystyle G=(E,V)} by replacing vertices by points and each edge  e = x y ∈ E {\displaystyle e=xy\in E} by a copy of the unit interval I = [ 0 , 1 ] {\displaystyle I=[0,1]} , where  0 {\displaystyle 0} is identified with the point associated to  x {\displaystyle x} and  1 {\displaystyle 1} with the point associated to  y {\displaystyle y} . That is, as topological spaces, graphs are exactly the simplicial 1-complexes and also exactly the one-dimensional CW complexes.[1]

Thus, in particular, it bears the quotient topology of the set

X 0 ⊔ ⨆ e ∈ E I e {\displaystyle X_{0}\sqcup \bigsqcup _{e\in E}I_{e}}

under the quotient map used for gluing. Here  X 0 {\displaystyle X_{0}} is the 0-skeleton (consisting of one point for each vertex  x ∈ V {\displaystyle x\in V} ),  I e {\displaystyle I_{e}} are the closed intervals glued to it, one for each edge  e ∈ E {\displaystyle e\in E} , and  ⊔ {\displaystyle \sqcup } is the disjoint union.[1]

The topology on this space is called the graph topology.

## Subgraphs and trees

[edit]

A subgraph of a graph  X {\displaystyle X} is a subspace Y ⊆ X {\displaystyle Y\subseteq X} which is also a graph and whose nodes are all contained in the 0-skeleton of  X {\displaystyle X} .  Y {\displaystyle Y} is a subgraph if and only if it consists of vertices and edges from  X {\displaystyle X} and is closed.[1]

A subgraph  T ⊆ X {\displaystyle T\subseteq X} is called a tree if it is contractible as a topological space.[1] This can be shown equivalent to the usual definition of a tree in graph theory, namely a connected graph without cycles.

## Properties

[edit]

* The associated topological space of a graph is connected (with respect to the graph topology) if and only if the original graph is connected.
* Every connected graph  X {\displaystyle X} contains at least one maximal tree  T ⊆ X {\displaystyle T\subseteq X} , that is, a tree that is maximal with respect to the order induced by set inclusion on the subgraphs of  X {\displaystyle X} which are trees.[1]
* If  X {\displaystyle X} is a graph and  T ⊆ X {\displaystyle T\subseteq X} a maximal tree, then the fundamental group π 1 ( X ) {\displaystyle \pi _{1}(X)} equals the free group generated by elements  ( f α ) α ∈ A {\displaystyle (f_{\alpha })_{\alpha \in A}} , where the  { f α } {\displaystyle \\{f_{\alpha }\\}} correspond bijectively to the edges of  X ∖ T {\displaystyle X\setminus T} ; in fact,  X {\displaystyle X} is homotopy equivalent to a wedge sum of circles.[1]
* Forming the topological space associated to a graph as above amounts to a functor from the category of graphs to the category of topological spaces.
* Every covering space projecting to a graph is also a graph.[1]

## See also

[edit]

* Graph homology
* Topological graph theory
* Nielsen–Schreier theorem, whose standard proof makes use of this concept.

## References

[edit]

1. ^ a b c d e f g Hatcher, Allen (2002). Algebraic Topology. Cambridge University Press. p. 83ff. ISBN 0-521-79540-0.