Simple Graphs and Their Notation

Simple Graphs as Vertex and Edge Sets

A graph represents a collection of objects together with selected pairwise relationships between them. The objects are the vertices; the relationships are the edges. In this tutorial, graphs are finite and simple. The word “simple” specifies the permitted form of an edge: it connects two distinct vertices, and a particular pair of vertices can be joined by at most one edge.

An edge \(uv\) is an unordered pair: \(uv\) and \(vu\) name the same edge. In particular, the order of the endpoint labels does not create a different relationship. The edge set \(E\) is itself a set, so listing the same pair twice does not create two edges. These conventions make a simple graph an appropriate model when the information of interest is just which distinct pairs are related, with each relationship recorded once.

The two restrictions are built into the requirement that each edge be a two-element subset. A loop would have the same endpoint twice, so it would be a one-element set rather than a two-element set. Repeating an edge would not add another element to a set. Other graph models can allow such features, but they are not simple graphs; those models have their own definitions.

Reading the Notation

The vertex set tells you which objects are included in the graph, even if some have no edges. The edge set tells you exactly which pairs are joined. The order counts vertices, while the size counts edges. Neither count is determined by the labels themselves: vertices named \(1,2,3\) do not mean the graph has size \(3\); the size comes from counting its distinct edges.

When the vertices are labelled with numbers, \(12\) is shorthand for \(\{1,2\}\), not the number twelve. For example, writing \(E=\{12,24\}\) specifies the two edges \(\{1,2\}\) and \(\{2,4\}\). Edge notation without braces is convenient, but the endpoints must belong to the stated vertex set.

Proof. If \(G\) is a simple graph, its definition says that \(V\) is finite and that \(E\) is a set of two-element subsets of \(V\). Each such subset contains two distinct vertices, so no edge is a loop. Because \(E\) is a set, a given two-element subset is either present once or absent; it cannot occur as two different edges. Conversely, suppose \(V\) is finite and the edges are distinct unordered pairs of distinct elements of \(V\), with no pair repeated. Each edge is then a two-element subset of \(V\), and the collection of these pairs is a set \(E\). Therefore \(G=(V,E)\) satisfies the definition of a simple graph. \(\square\)

For any fixed finite vertex set, the definition also gives a direct count of the possible simple graphs on that set. There is one possible edge for each unordered pair of distinct vertices. Each possible pair can either be included in \(E\) or omitted, independently of the other pairs.

Proof. An edge must be a two-element subset of \(V\), and there are \(\binom{n}{2}\) such subsets: there are \(n(n-1)\) ordered choices of two distinct vertices, and each unordered pair is counted twice, once in each order. For each of these \(\binom{n}{2}\) candidate edges, a graph’s edge set makes exactly one choice: include it or omit it. Thus each candidate pair contributes two choices, giving \(2^{\binom{n}{2}}\) edge sets. When \(n=0\) or \(n=1\), there are no candidate pairs, and there is exactly one choice of edge set, namely \(E=\varnothing\); the formula gives \(2^0=1\) in both cases. \(\square\)

Labels, Edge Sets, and Counting

Different edge sets on the same vertex set describe different graphs. For instance, changing one edge changes which pair is related, even when the vertex set is unchanged. On the other hand, changing vertex labels alone does not change the kind of information being represented: labels identify the objects, while the edge set records the selected pairs. When interpreting a graph, read \(V\) and \(E\) together rather than inferring one from the other.

The formula for the number of possible graphs can be checked on a small vertex set. With \(V=\{1,2,3\}\), the possible edges are \(12,13,23\). Each can be selected or omitted, so there are \(2\cdot2\cdot2=8\) possible edge sets, including the empty edge set and the set containing all three pairs. This agrees with \(2^{\binom{3}{2}}=2^3=8\).

Common Pitfalls

Counting written entries instead of distinct edges. In the last example, counting the four entries in the display as four separate edges gives the wrong size. The correction is to use the set \(E=\{pq,qr,rs\}\) and count its distinct elements: \(m=3\).

Forgetting vertices with no listed edges. In the second example, \(e\) remains a vertex because it belongs to \(V\), even though it appears in no edge. Removing it would change the vertex set and the order.

Reading \(uv\) as an ordered pair. In a simple graph \(uv\) and \(vu\) denote the same unordered edge. Listing both does not create two edges. Also, \(uu\) is not a permitted edge: it does not have two distinct endpoints.

Confusing order with size. The order \(n\) is \(|V|\); the size \(m\) is \(|E|\). Count the elements of the relevant set rather than using the vertex labels or assuming that one count determines the other.