Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

Section 14.1 Basics and examples

graph (working definition)
a diagram consisting of a finite collection of points linked by line segments or arcs
graph (formal definition)
an ordered pair \((V,E)\text{,}\) where \(V\) is a finite set and \(E\) is a finite, unordered list of subsets of \(V\text{,}\) each of which has exactly \(1\) or \(2\) elements
vertex
a point in a graph (i.e. an element of \(V\))
node
synonym for vertex
edge
a line or arc linking two vertices (i.e. an element of \(E\))
empty graph
the graph \((\emptyset,\emptyset)\text{,}\) with no vertices and no edges

Warning 14.1.1.

The list \(E\) is not a set, since duplicate entries in this list have a graphical meaning; see below.
An element \(e \in E\) represents an edge as follows. If \(e\) consists of exactly two elements of \(V\text{,}\) draw a line between these two vertices. If \(e\) consists of exactly one element of \(V\text{,}\) draw a line from this vertex to itself.

Example 14.1.2. A very basic graph.

The graph \(G = (V,E)\text{,}\) where
\begin{align*} V \amp = \{ v_1, v_2, v_3 \}, \amp E \amp = \bigl\{ \{v_1,v_2\}, \{v_1,v_3\}, \{v_2,v_3\} \bigr\}, \end{align*}
has three vertices and three edges.
Diagram illustrating a basic example graph.
Figure 14.1.3. Diagram of the graph \(G = (V,E)\text{.}\)

Example 14.1.4. A slightly more complicated example graph.

The graph \(G = (V,E)\text{,}\) where
\begin{align*} V \amp = \{ v_1, v_2, v_3, v_4 \}, \amp E \amp = \bigl\{ \{v_1, v_2\}, \{v_1, v_2\}, \{v_1, v_2\}, \{ v_3 \}, \{ v_3 \} \bigr\}, \end{align*}
has four vertices and five edges.
Diagram illustrating a slightly more complicated example graph.
Figure 14.1.5. Diagram of the graph \(G = (V,E)\text{.}\)

Worked Example 14.1.6. Using a graph to solve a problem.

Suppose we have jugs \(A,B,C\) with capacities \(8,5,3\) litres, respectively. Jug \(A\) is full of water and jugs \(B,C\) are empty. Can we divide the water into two exactly equal parts? If so, find the most efficient pouring sequence.
Solution.
Construct a graph with points labelled by elements \((a,b,c) \in \N \times \N \times \N\text{,}\) where \(a,b,c\) are the volumes of water in jugs \(A,B,C\text{,}\) respectively. Join two points with a line segment if we can obtain one set of volumes from the other in a single pour. We will ignore pours that return us to a configuration previously achievable by fewer pours.
A graph where nodes are jug fill states and edges represent being able to obtain one state from another by a single pour.
Figure 14.1.7. Graph to track possible jug fill states.
Following the left leg of the graph gets us to the desired configuration in \(7\) pours.
<Prev^TopNext>