Graph (topology)

In topology, a subject in mathematics, a graph is a topological space which arises from a usual graph ${\displaystyle G=(E,V)}$ by replacing vertices by points and each edge ${\displaystyle e=xy\in E}$ by a copy of the unit interval ${\displaystyle I=[0,1]}$, where ${\displaystyle 0}$ is identified with the point associated to ${\displaystyle x}$ and ${\displaystyle 1}$ with the point associated to ${\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

${\displaystyle X_{0}\sqcup \bigsqcup _{e\in E}I_{e}}$

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

The topology on this space is called the graph topology.[2]

Subgraphs and -trees

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

A subgraph ${\displaystyle T\subseteq X}$ is called a tree iff it is contractible as a topological space.[1]

Properties

• Every connected graph ${\displaystyle X}$ contains at least one maximal tree ${\displaystyle T\subseteq X}$, that is, a tree that is maximal with respect to the order induced by set inclusion on the subgraphs of ${\displaystyle X}$ which are trees.[1]
• If ${\displaystyle X}$ is a graph and ${\displaystyle T\subseteq X}$ a maximal tree, then the fundamental group ${\displaystyle \pi _{1}(X)}$ equals the free group generated by elements ${\displaystyle (f_{\alpha })_{\alpha \in A}}$, where the ${\displaystyle \{f_{\alpha }\}}$ correspond bijectively to the edges of ${\displaystyle X\setminus T}$; in fact, ${\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.[2]
• The associated topological space of a graph is connected (with respect to the graph topology) if and only if the original graph is connected.[2]
• Every covering space projecting to a graph is also a graph.[1]

Applications

Using the above properties of graphs, one can prove the Nielsen–Schreier theorem.[1]

See also

• Graph homology
• Topological graph theory

References

1. Hatcher, Allen (2002). Algebraic Topology. Cambridge University Press. p. 83ff. ISBN 0-521-79540-0.
2. Michael Slone (8 May 2003). "graph topology". PlanetMath. Retrieved 1 February 2017.