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\ne 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	Digraph
Related topic	Tree
Related topic	SpanningTree
Related topic	ConnectedGraph
Related topic	Cycle
Related topic	GraphTheory
Related topic	GraphTopology
Related topic	Subgraph
Related topic	SimplePath
Related topic	EulerPath
Related topic	Diameter3
Related topic	DistanceInAGraph
Related topic	GraphHomomorphism
Related topic	Pseudograph
Related topic	Multigraph
Related topic	OrderOf
Defines	edge
Defines	vertex
Defines	endvertex
Defines	adjacent
Defines	incident
Defines	join
Defines	vertices
Defines	simple graph