Vertex-Edge Models of Graphs

Graphs as Vertex-and-Edge Models

A graph records which objects are present and which pairs of objects are connected. The objects are represented by vertices; the connections are represented by edges. A drawing can help us see those connections, but the drawing itself is not the graph: the underlying data are the vertex set and edge set.

“Unordered” means that \(uv\) and \(vu\) describe the same edge, not two different edges. The order in which vertices or edges are written in a list also carries no extra information. For instance, \(E=\{ab,bc\}\) and \(E=\{bc,ab\}\) are the same edge set. When a vertex set is specified, every endpoint in the edge set must belong to it.

A vertex does not need to occur in any edge. Such a vertex is called isolated. It remains part of the graph, even though no line touches it in a drawing. The empty vertex set is also allowed; its edge set must be empty. At the other extreme, a graph with one vertex and no edges is a valid graph.

From the Data to a Drawing, and Back

To draw a graph from \((V,E)\), make one marked point for each vertex, label each point by its vertex, and draw a line or curve between the points for each edge in \(E\). Do not add a joining line for a pair that is not an edge. The locations of the points and the shapes of the lines are choices made for convenience; they do not change the vertex set or edge set.

To read a drawing, first record every marked, labelled vertex, including any with no line attached. Then inspect the drawn joins and record the pair of endpoint labels for each one. A line that crosses another line is not automatically a vertex at the crossing. It counts as a vertex only if a point there is marked and specified as a vertex of the graph. Likewise, a crossing does not by itself add an edge.

Proof. Suppose first that every item in the list is an unordered pair of distinct elements of \(V\). Collect the listed pairs into a set \(E\). By construction, \(E\) consists of unordered pairs of distinct vertices from \(V\), so \(G=(V,E)\) is a graph in the stated model. A set records which elements it contains, not the order in which they were presented. It also contains an element only once, even if that element appears multiple times in the list. Thus reordering the list or repeating an item does not change \(E\). Conversely, if an item is not a pair of distinct elements of \(V\), then it is not an allowed edge in this model; the proposed list therefore cannot define an edge set of the required form. \(\square\)

This condition is a useful check before drawing: validate the endpoints first, then make one join for each distinct edge. The next examples carry out both directions of the translation.

Why a Drawing Is Not the Graph

Proof. Let the common labelled vertex set be \(V\), and let \(E_1\) and \(E_2\) be the edge sets read from the two drawings. By hypothesis, a pair \(uv\) is represented by a drawn join in the first drawing exactly when that same pair is represented by a drawn join in the second. Hence \(uv\in E_1\) exactly when \(uv\in E_2\), for every unordered pair of labels from \(V\). Therefore \(E_1=E_2\). The two drawings have the same vertex set and edge set, so they encode the same graph. \(\square\)

This result explains why a graph can have many different-looking drawings. Moving a point, bending a line, or changing the layout does not alter the model unless the labels or the pairs joined change. Conversely, a neat-looking drawing is not a substitute for specifying which vertices and edges it contains: the sets \((V,E)\) remove any uncertainty about the intended data.

Common Pitfalls

Omitting isolated vertices. Suppose the stated data are \(V=\{a,b,c,d\}\) and \(E=\{ab,bc\}\). It would be wrong to read the graph from the edge list alone and report \(V=\{a,b,c\}\). The correction is to keep the given vertex set: \(d\) is an isolated vertex. A complete description must retain it even though no edge uses its label.

Treating a crossing as a connection. In the crossing example, the drawn diagonals have endpoint pairs \(pq\) and \(rs\). Their intersection is not a new vertex, so it does not split either diagonal into additional edges. Only marked vertices and stated joins determine the model. If a diagram uses a crossing as a vertex, that point must be indicated and included in the vertex set.

Reversing an edge or duplicating it in a list. Since edges are unordered pairs, \(uv\) and \(vu\) are one and the same edge. Likewise, writing \(E=\{ab,bc,ab\}\) does not create two distinct \(ab\) edges: as a set this is \(\{ab,bc\}\). Do not interpret a change in listing order or a repeated entry as a new connection.

A reliable translation in either direction is therefore systematic:

1. Write down every vertex label before deciding which vertices are isolated.
2. Record each distinct joined pair once, without assigning significance to endpoint order.
3. Check that every edge has two distinct endpoints from the stated vertex set.
4. When drawing, include exactly those joins; when reading a drawing, do not infer extra vertices or edges from unmarked crossings.