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. 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. The topology on this space is called the graph topology.
Subgraphs and trees 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. A subgraph T ⊆ X {\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 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. 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 ∖ T {\displaystyle X\setminus T} 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
