topology In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ho ...

, a branch of mathematics, a graph is a

topological space In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called po ...

which arises from a usual

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

G = (E, V)

by replacing vertices by points and each edge

e = xy \in E

by a copy of the

unit interval In mathematics, the unit interval is the closed interval , that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1. It is often denoted ' (capital letter ). In addition to its role in real analys ...

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-complex es and also exactly the one-dimensional

CW complex A CW complex (also called cellular complex or cell complex) is a kind of a topological space that is particularly important in algebraic topology. It was introduced by J. H. C. Whitehead (open access) to meet the needs of homotopy theory. This cla ...

es. Thus, in particular, it bears the

quotient topology In topology and related areas of mathematics, the quotient space of a topological space under a given equivalence relation is a new topological space constructed by endowing the quotient set of the original topological space with the quotient t ...

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 intervals ("closed one-dimensional unit balls") glued to it, one for each edge

e \in E

, and

\sqcup

is the

disjoint union In mathematics, a disjoint union (or discriminated union) of a family of sets (A_i : i\in I) is a set A, often denoted by \bigsqcup_ A_i, with an injection of each A_i into A, such that the images of these injections form a partition of A ...

. The

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 In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bi ...

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.

Properties

* The associated topological space of a graph is

connected Connected may refer to: Film and television * ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular'' * '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film * ''Connected'' (2015 TV ...

(with respect to the graph topology) if and only if the original graph is

. * 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 In the mathematical field of algebraic topology, the fundamental group of a topological space is the group of the equivalence classes under homotopy of the loops contained in the space. It records information about the basic shape, or holes, of ...

\pi_1(X)

equals the

free group In mathematics, the free group ''F'S'' over a given set ''S'' consists of all words that can be built from members of ''S'', considering two words to be different unless their equality follows from the group axioms (e.g. ''st'' = ''suu''− ...

generated by elements

(f_\alpha)_

, where the

\

correspond

bijective In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...

ly to the edges of

X \setminus T

; in fact,

X

homotopy equivalent In topology, a branch of mathematics, two continuous functions from one topological space to another are called homotopic (from grc, ὁμός "same, similar" and "place") if one can be "continuously deformed" into the other, such a defo ...

to a

wedge sum In topology, the wedge sum is a "one-point union" of a family of topological spaces. Specifically, if ''X'' and ''Y'' are pointed spaces (i.e. topological spaces with distinguished basepoints x_0 and y_0) the wedge sum of ''X'' and ''Y'' is the qu ...

circle A circle is a shape consisting of all points in a plane that are at a given distance from a given point, the centre. Equivalently, it is the curve traced out by a point that moves in a plane so that its distance from a given point is const ...

s. * Forming the topological space associated to a graph as above amounts to a

functor In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) are associated to topological spaces, an ...

from the

category Category, plural categories, may refer to: Philosophy and general uses *Categorization, categories in cognitive science, information science and generally * Category of being * ''Categories'' (Aristotle) * Category (Kant) * Categories (Peirce) ...

of graphs to the

category of topological spaces In mathematics, the category of topological spaces, often denoted Top, is the category whose objects are topological spaces and whose morphisms are continuous maps. This is a category because the composition of two continuous maps is again con ...

. * Every

covering space A covering of a topological space X is a continuous map \pi : E \rightarrow X with special properties. Definition Let X be a topological space. A covering of X is a continuous map : \pi : E \rightarrow X such that there exists a discrete sp ...

projecting to a graph is also a graph.

Applications

Using the above properties of graphs, one can prove the

Nielsen–Schreier theorem In group theory, a branch of mathematics, the Nielsen–Schreier theorem states that every subgroup of a free group is itself free. It is named after Jakob Nielsen and Otto Schreier. Statement of the theorem A free group may be defined from a ...

References

{{cite web , url=http://planetmath.org/graphtopology , title=graph topology , date=8 May 2003 , author=Michael Slone , website=PlanetMath , access-date=1 February 2017 Topological spaces

Subgraphs and trees

Properties

Applications

See also

References