graph

A graph $G$ is an ordered pair of disjoint sets $(V,E)$ such that $E$ is a subset of the set $V^{(2)}$ of unordered pairs of $V$. $V$ and $E$ are always assumed to be finite, unless explicitly stated otherwise. The set $V$ is the set of vertices (sometimes called nodes) and $E$ is the set of edges. If $G$ is a graph, then $V=V(G)$ is the vertex set of $G$, and $E=E(G)$ is the edge set. Typically, $V(G)$ is defined to be nonempty. If $x$ is a vertex of $G$, we sometimes write $x\in G$ instead of $x\in V(G)$.

An edge $\{x,y\}$ (with $x\neq y$) is said to join the vertices $x$ and $y$ and is denoted by $xy$. One says that the edges $xy$ and $yx$ are equivalent; the vertices $x$ and $y$ are the endvertices of this edge. If $xy\in E(G)$, then $x$ and $y$ are adjacent, or neighboring, vertices of $G$, and the vertices $x$ and $y$ are incident with the edge $xy$. Two edges are adjacent if they have at least one common endvertex. Also, $x\sim y$ means that the vertex $x$ is adjacent to the vertex $y$.

Notice that this definition allows pairs of the form $\{x,x\}$, which would correspond to a node joining to itself. Some authors explicitly disallow this in their definition of a graph.

Some graphs.

Note: Some authors include multigraphs in their definition of a graph. In this notation, the above definition corresponds to that of a simple graph. A graph is then simple if there is at most one edge joining each pair of nodes.

Adapted with permission of the author from by Béla Bollobás, published by Springer-Verlag New York, Inc., 1998.

 Title graph Canonical name Graph Date of creation 2013-03-22 11:57:54 Last modified on 2013-03-22 11:57:54 Owner mathcam (2727) Last modified by mathcam (2727) Numerical id 34 Author mathcam (2727) Entry type Definition Classification msc 05C99 Related topic LoopOfAGraph Related topic NeighborhoodOfAVertex Related topic EulersPolyhedronTheorem Related topic Related topic Tree Related topic SpanningTree Related topic ConnectedGraph Related topic Cycle Related topic GraphTheory Related topic GraphTopology Related topic Related topic SimplePath Related topic EulerPath Related topic Diameter3 Related topic DistanceInAGraph Related topic GraphHomomorphism Related topic Related topic Multigraph Related topic OrderOf Defines edge Defines vertex Defines endvertex Defines adjacent Defines incident Defines join Defines vertices Defines simple graph