A graph G is an ordered pairMathworldPlanetmath 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 xG instead of xV(G).

An edge {x,y} (with xy) is said to join the vertices x and y and is denoted by xy. One says that the edges xy and yx are equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath; the vertices x and y are the endvertices of this edge. If xyE(G), then x and y are adjacent, or neighboring, vertices of G, and the vertices x and y are incidentPlanetmathPlanetmath with the edge xy. Two edges are adjacent if they have at least one common endvertex. Also, xy 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 multigraphsMathworldPlanetmath 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 DigraphMathworldPlanetmath
Related topic Tree
Related topic SpanningTree
Related topic ConnectedGraph
Related topic Cycle
Related topic GraphTheory
Related topic GraphTopology
Related topic SubgraphMathworldPlanetmath
Related topic SimplePath
Related topic EulerPath
Related topic Diameter3
Related topic DistanceInAGraph
Related topic GraphHomomorphism
Related topic PseudographMathworldPlanetmath
Related topic Multigraph
Related topic OrderOf
Defines edge
Defines vertex
Defines endvertex
Defines adjacent
Defines incident
Defines join
Defines vertices
Defines simple graph