Graph (topology)

In topology, a branch of mathematics, a graph is a topological space which arises from a usual graph $G = (E, V)$ by replacing vertices by points and each edge $e = xy \in E$ by a copy of the unit interval I = ,1/math>, where $0$ is identified with the point associated to $x$ and $1$ with the point associated to $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
:$X_0 \sqcup \bigsqcup_ I_e$
under the quotient map used for gluing. Here $X_0$ is the 0-skeleton (consisting of one point for each vertex $x \in V$), $I_e$ are the closed intervals glued to it, one for each edge $e \in E$, and $\sqcup$ is the disjoint union.

The topology on this space is called the graph topology.

Subgraphs and trees

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

A subgraph $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 $X$ contains at least one maximal tree $T \subseteq X$, that is, a tree that is maximal with respect to the order induced by set inclusion on the subgraphs of $X$ which are trees.
* If $X$ is a graph and $T \subseteq X$ a maximal tree, then the fundamental group $\pi_1(X)$ equals the free group generated by elements $(f_\alpha)_$, where the $\$ correspond bijectively to the edges of $X \setminus T$; in fact, $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

{{cite book , last=Hatcher , first=Allen , year=2002 , title=Algebraic Topology , publisher=Cambridge University Press , page=83ff , isbn=0-521-79540-0

Topological spaces