Graph (topology) explained

G = (E, V) by replacing vertices by points and each edge e = xy \in E by a copy of the unit interval I = [ 0 , 1 ] , 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 s qcup _{e} 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)} _{\alpha} , where the \{f _{\alpha\}} 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

^[1]

Notes and References

1. Book: Hatcher, Allen . 2002 . Algebraic Topology . Cambridge University Press . 83ff. . 0-521-79540-0.