5.1: The Basics of Graph Theory

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

See Section 4.5 to review some basic terminology about graphs.

A graph $$G$$ consists of a pair $$(V,E)$$, where $$V$$ is the set of vertices and $$E$$ the set of edges. We write $$V(G)$$ for the vertices of $$G$$ and $$E(G)$$ for the edges of $$G$$ when necessary to avoid ambiguity, as when more than one graph is under discussion.

If no two edges have the same endpoints we say there are no multiple edges, and if no edge has a single vertex as both endpoints we say there are no loops. A graph with no loops and no multiple edges is a simple graph. A graph with no loops, but possibly with multiple edges is a multigraph. The condensation of a multigraph is the simple graph formed by eliminating multiple edges, that is, removing all but one of the edges with the same endpoints. To form the condensation of a graph, all loops are also removed. We sometimes refer to a graph as a general graph to emphasize that the graph may have loops or multiple edges.

The edges of a simple graph can be represented as a set of two element sets; for example, $(\{v_1,\ldots,v_7\},\{\{v_1,v_2\},\{v_2,v_3\},\{v_3,v_4\},\{v_3,v_5\}, \{v_4,v_5\},\{v_5,v_6\},\{v_6,v_7\}\})\nonumber$ is a graph that can be pictured as in Figure $$\PageIndex{1}$$. This graph is also a connected graph: each pair of vertices $$v$$, $$w$$ is connected by a sequence of vertices and edges, $$v=v_1,e_1,v_2,e_2,\ldots,v_k=w$$, where $$v_i$$ and $$v_{i+1}$$ are the endpoints of edge $$e_{i}$$. The graphs shown in Figure 4.5.2 are connected, but the figure could be interpreted as a single graph that is not connected.

A graph $$G=(V,E)$$ that is not simple can be represented by using multisets: a loop is a multiset $$\{v,v\}=\{2\cdot v\}$$ and multiple edges are represented by making $$E$$ a multiset. The condensation of a multigraph may be formed by interpreting the multiset $$E$$ as a set.

This page titled 5.1: The Basics of Graph Theory is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by David Guichard via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.