Misplaced Pages

In topology, a branch of 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=}$, 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.

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 of one point for each vertex ${\displaystyle x\in V}$), ${\displaystyle I_{e}}$ are the closed intervals glued to it, one for each edge ${\displaystyle e\in E}$, and ${\displaystyle \sqcup }$ is the disjoint union.

The topology on this space is called the graph topology.

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.

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

Properties

• 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 ${\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.
• 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.
• 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.

See also

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

References

1. ^ Hatcher, Allen (2002). Algebraic Topology. Cambridge University Press. p. 83ff. ISBN 0-521-79540-0.

• Topological spaces