Before exploring the deep results of graph theory, we need to build a precise vocabulary. Like any area of mathematics, graph theory has specific definitions that let us communicate ideas clearly and without ambiguity.
In this article, we establish the formal language we will use throughout the series.
Why Do We Need a Formal Language? #
Without a shared vocabulary, communication in graph theory would be imprecise and ambiguous. A formal language is indispensable for at least four reasons:
- Modeling: real problems (computer networks, delivery routes, dependencies between tasks) can only be analyzed mathematically after they are translated into a graph with precise definitions.
- Communication: when two researchers say “neighborhood of \(v\)”, the definitions guarantee that both understand exactly the same set.
- Proofs: without rigorous definitions, proofs lose their validity; every step of a proof rests on the exact definition of the terms used.
- Implementation: the formal definitions directly guide the data structures (adjacency lists, incidence matrices) that graph algorithms use.
These concepts have direct counterparts in computing: the neighborhood \(N(v)\) is exactly the adjacency list used in algorithms such as Breadth-First Search (BFS) and Depth-First Search (DFS); cliques are the core of community detection algorithms in social networks; and independent sets underlie the graph coloring problem, in which adjacent vertices cannot receive the same color, a restriction present in task scheduling, radio frequency allocation, and much more.
Formal Definition of a Graph #
A simple graph, or graph, \(G\) is a pair \((V, E)\), denoted \(G = (V, E)\), where \(V\) is a finite nonempty set of elements called vertices (also called nodes or points) and \(E\) is a set of unordered pairs of distinct elements of \(V\), called edges.
- Vertices = nodes = points: the three terms are synonyms.
- Number of vertices of \(G\): \(|V(G)| = n\).
- Number of edges of \(G\): \(|E(G)| = m\).
- When there are several graphs \(G_1, G_2, \ldots, G_k\), we denote their vertex and edge sets respectively by \((V(G_1), E(G_1))\), \((V(G_2), E(G_2))\), …, \((V(G_k), E(G_k))\).
- Graphs = simple graphs: unless stated otherwise, “graph” always means simple graph in this series.
Given a graph \(G = (V, E)\), each edge \(e \in E\) will be denoted by the pair \(e = (v, w)\) that forms it, with \(v, w \in V\). In this case, the vertices \(v\) and \(w\) are the endpoints of the edge \(e\). The edge \(e\) is said to be incident to the vertices \(v\) and \(w\).
Example 1
Let \(G = (V, E)\) with:
$$V = \{a,\ b,\ c,\ d,\ e\}$$$$E = \{(a,b),\ (b,c),\ (a,c),\ (a,e),\ (c,d),\ (e,d)\}$$
In this graph:
- \(a\) and \(b\) are adjacent; \(b\) and \(d\) are not adjacent
- The edge \((c,d)\) is incident to \(c\) and to \(d\); the endpoints of \((c,d)\) are \(c\) and \(d\)
- \(n = |V| = 5\) and \(m = |E| = 6\)
The figure below shows the geometric representation of \(G\).
Geometric Representation #
The usual way to represent a graph is geometric (in the plane): each vertex corresponds to a point in the plane and each edge \((v, w)\) corresponds to a line joining the points that correspond to the vertices \(v\) and \(w\).
Example 2
Let \(G\) be the graph of Example 1, with \(V = \{a,b,c,d,e\}\) and \(E = \{(a,b),(b,c),(a,c),(a,e),(c,d),(e,d)\}\). This graph admits multiple valid geometric representations: the vertices can be placed at different positions in the plane (for example, in the shape of a pentagon or in any other configuration), as long as the connections are preserved. The geometric representation of a graph is not unique.
The two representations below correspond to the same graph \(G\): same vertices, same edges, different positions.
If we relax the definition of a simple graph to admit equal unordered pairs of distinct elements of \(V\), called parallel edges, and pairs of equal elements \((v, v)\), called loops, we obtain a multigraph. In this series, unless noted otherwise, we work only with simple graphs.
Example 3
Let \(G = (V, E)\) with \(V = \{a, b, c, d\}\) and
$$E = \{(a,b),\ (a,b),\ (b,c),\ (c,d),\ (d,a),\ (c,c)\}$$The two occurrences of \((a,b)\) are parallel edges; \((c,c)\) is a loop.
The multigraph below illustrates parallel edges and a loop.
Neighborhood and Isolation #
Let \(G = (V, E)\) be a graph. The vertices \(v\) and \(w \in V\) are said to be adjacent or neighbors if \((v, w) \in E\). We call the adjacency or neighborhood of \(v\) in \(G\) the set:
$$N(v) = \{w \in V \mid (v, w) \in E\}$$When more than one graph is at play, we write \(N_G(v)\) to indicate the neighborhood of \(v\) in the graph \(G\).
Example 4
Let \(G\) be the graph of Example 1. We compute the neighborhood of each vertex:
- \(N(a) = \{b, c, e\}\)
- \(N(b) = \{a, c\}\)
- \(N(c) = \{b, a, d\}\)
- \(N(d) = \{c, e\}\)
- \(N(e) = \{a, d\}\)
The following figure shows \(G\) with the vertex \(a\) and its edges highlighted, illustrating \(N(a) = \{b, c, e\}\).
A vertex \(v\) with \(N(v) = \emptyset\) is called an isolated vertex, since it is not connected to any other vertex.
Example 5
Let \(G = (V, E)\) with \(V = \{1, 2, 3, 4, 5\}\) and
$$E = \{(1,2),\ (2,3),\ (1,3),\ (1,4),\ (3,4)\}$$We compute \(N(5) = \emptyset\). Hence, 5 is an isolated vertex in \(G\).
Vertex 5 (highlighted) has no incident edges, confirming \(N(5) = \emptyset\).
A vertex \(v\) of \(G\) is said to be universal when
$$N(v) = V - \{v\}$$that is, \(v\) is adjacent to all the other vertices of the graph.
Example 6
Let \(G = (V, E)\) with \(V = \{1, 2, 3, 4, 5\}\) and
$$E = \{(1,2),\ (1,3),\ (1,4),\ (1,5),\ (2,3),\ (3,4),\ (4,5)\}$$We compute \(N(1) = \{2, 3, 4, 5\} = V - \{1\}\). Hence, 1 is a universal vertex in \(G\).
Vertex 1 (highlighted) is connected to all the others: \(N(1) = V - \{1\}\).
In a graph with at least two vertices we cannot have an isolated vertex and a universal vertex at the same time: the universal vertex would be a neighbor of the isolated one, which by definition has no neighbors. The exception is the single-vertex graph, in which \(N(v) = \emptyset = V - \{v\}\) and the vertex is both.
The flowchart below summarizes how to classify any vertex \(v\) as isolated, universal, or neither.
flowchart TD
A["Vertex v in G"] --> B{"N(v) = ∅ ?"}
B -- "Yes" --> C["Isolated
no neighbors"]
B -- "No" --> D{"N(v) = V − {v} ?"}
D -- "Yes" --> E["Universal
adjacent to all"]
D -- "No" --> F["Neither isolated
nor universal"]
The Complement Graph #
The complement of \(G\), denoted \(\bar{G}\), is the graph with the same vertex set \(V(G)\), such that two distinct vertices are adjacent in \(\bar{G}\) if and only if they are not adjacent in \(G\):
$$V(\bar{G}) = V(G)$$$$E(\bar{G}) = \{(v, w) \mid v, w \in V(G)\ \text{and}\ (v, w) \notin E(G)\}$$
Example 7
Let \(G\) be the graph of Example 1: \(V = \{a,b,c,d,e\}\) and \(E(G) = \{(a,b),(b,c),(a,c),(a,e),(c,d),(e,d)\}\).
The complete graph on 5 vertices would have \(\binom{5}{2} = 10\) edges. Since \(m = 6\), the complement \(\bar{G}\) has \(10 - 6 = 4\) edges, exactly the pairs that do not appear in \(G\):
$$E(\bar{G}) = \{(a,d),\ (b,d),\ (b,e),\ (c,e)\}$$The two graphs below illustrate \(G\) and \(\bar{G}\): note that the edges present in one are absent from the other.
Subgraphs #
One of the most important notions is that of a subgraph: parts of a graph obtained by keeping a subset of its vertices and edges.
Let \(G\) and \(H\) be graphs. \(H\) is said to be a subgraph of \(G\), denoted \(H \subseteq G\), if:
- \(V(H) \subseteq V(G)\)
- \(E(H) \subseteq E(G)\)
Example 8
Let \(G\) and \(H\) be the following graphs:
\(V(G) = \{a, b, c, d, e\}\),
\(E(G) = \{(a,b),\ (b,c),\ (a,c),\ (c,d),\ (e,d),\ (a,e)\}\)
\(V(H) = \{a, b, c, d\}\), \(E(H) = \{(a,b),\ (b,c)\}\)
Since \(V(H) \subseteq V(G)\) and \(E(H) \subseteq E(G)\), we conclude that \(H\) is a subgraph of \(G\).
The figure shows \(G\) on the left and \(H\) on the right. Note that \(H\) has only 2 of the 6 edges of \(G\), and the vertex \(d\) is isolated in \(H\).
Induced Subgraph #
Let \(G\) be a graph and \(A \subseteq V(G)\), that is, a subset of the vertices of \(G\). The subgraph of \(G\) induced by \(A\), denoted \(G[A]\), is defined by:
$$V(G[A]) = A$$$$E(G[A]) = \{(x, y) \in E(G) \mid x \in A\ \text{and}\ y \in A\}$$
\(G[A]\) inherits all the edges of \(G\) whose two endpoints belong to \(A\).
Example 9
Considering the graph \(G\) of Example 8, let \(A = \{a, b, c, d\}\) (\(A \subset V(G)\)). The subgraph \(F = G[A]\) induced by \(A\) has:
\(V(F) = \{a, b, c, d\}\)
\(E(F) = \{(a,b),\ (b,c),\ (a,c),\ (c,d)\}\)
Observe that \((a,c)\) and \((c,d)\) belong to \(E(F)\) because both endpoints of each of these edges belong to \(A\) and they exist in \(E(G)\).
In the figure, the vertices of \(A\) are highlighted in \(G\) (left); on the right, \(F = G[A]\) with all 4 inherited edges.
The subgraph \(H\) of Example 8 and the subgraph \(F\) of Example 9 have the same vertex set \(\{a,b,c,d\}\), but they are not equal:
- \(E(H) = \{(a,b),\ (b,c)\}\): \(H\) is not the subgraph of \(G\) induced by the set \(\{a,b,c,d\}\), because the edges \((a,c)\) and \((c,d)\) exist in \(G\) with both endpoints in \(\{a,b,c,d\}\), but were omitted from \(H\).
- \(E(F) = \{(a,b),\ (b,c),\ (a,c),\ (c,d)\}\): \(F\) is an induced subgraph because it inherited all the edges of \(G\) among the vertices of \(A\).
The comparison below places \(G\), \(H\), and \(F\) side by side: \(H\) and \(F\) have the same \(V\), but \(H\) omits edges that \(F\) necessarily inherits.
Spanning Subgraph #
Let \(G\) and \(H\) be graphs. \(H\) is said to be a spanning subgraph of \(G\) if \(H\) is a subgraph of \(G\) and \(V(H) = V(G)\), that is, \(H\) contains all the vertices of \(G\), but possibly fewer edges.
Example 10
Considering the graph \(G\) of Example 8, let \(H\) be given by:
\(V(H) = V(G) = \{a, b, c, d, e\}\), \(E(H) = \{(a,b),\ (a,c),\ (c,d)\}\)
Since \(V(H) = V(G)\) and \(E(H) \subseteq E(G)\), \(H\) is a spanning subgraph of \(G\).
The spanning subgraph \(H\) keeps all 5 vertices of \(G\), but preserves only 3 of the 6 edges, and the vertex \(e\) is isolated.
The following diagram summarizes the relationships among the types of subgraph studied and their special cases.
flowchart TD
A["Subgraph H ⊆ G
V(H) ⊆ V(G) and E(H) ⊆ E(G)"] --> B["Induced Subgraph G[A]
inherits all edges of G
whose two endpoints are in A"]
A --> C["Spanning Subgraph
V(H) = V(G)
possibly fewer edges"]
B --> D["Clique A
G[A] is complete (= Kk)"]
B --> E["Independent Set S
G[S] is null (= Ns)"]
Special Graphs: Complete and Null #
A graph \(G\) is said to be complete if all of its pairs of distinct vertices are adjacent. In other words, all of its vertices are universal. A complete graph with \(n\) vertices is denoted by \(K_n\).
Number of edges: \(|E(K_n)| = \binom{n}{2} = \dfrac{n(n-1)}{2}\)
Example 11
- \(K_1\): 1 vertex, 0 edges
- \(K_2\): 2 vertices, 1 edge
- \(K_3\): 3 vertices, 3 edges
- \(K_4\): 4 vertices, 6 edges
- \(K_5\): 5 vertices, 10 edges
The first five complete graphs are shown below.
Clique #
Let \(G\) be a graph and \(A \subseteq V(G)\) a subset of vertices. \(A\) is a clique of \(G\) if \(G[A]\) is a complete graph: every pair of vertices in \(A\) is adjacent.
Example 12
Let \(G\) be a graph with \(V = \{a,b,c,d,e,f,g,h\}\) and edges:
$$(a,b),\ (a,c),\ (a,d),\ (b,c),\ (b,d),\ (c,d),\ (c,e),\ (e,f),\ (c,f),\ (c,h),\ (h,g),\ (g,f)$$The following subsets are cliques of \(G\):
- \(A_1 = \{a, b, c, d\}\): clique of size 4 (\(G[A_1] = K_4\))
- \(A_2 = \{c, e, f\}\): clique of size 3 (\(G[A_2] = K_3\))
- \(A_3 = \{g, h\}\): clique of size 2
Other \(A_i\) are also possible: any subset of \(A_1\) with 2 or 3 vertices (for example \(\{a,b,c\}\), \(\{a,c,d\}\)) forms a clique. A clique is maximal when it is not contained in any larger clique, and maximum when no clique of the graph has more vertices than it does. \(A_1\), \(A_2\), and \(A_3\) are maximal, as are \(\{c,h\}\) and \(\{f,g\}\), but only \(A_1\), with 4 vertices, is maximum. Finding a maximum clique in a large graph is a hard problem: no efficient algorithm is known for the general case (see the entry Clique problem).
The figure below shows \(G\) with the vertices colored by group: \(A_1\) in blue, \(A_2\) in orange, \(A_3\) in green; the vertex \(c\) (shared by \(A_1\) and \(A_2\)) is highlighted.
Null Graph #
The natural counterpart of \(K_n\) is the null graph: instead of all pairs being adjacent, no pair is adjacent.
A graph \(G\) is said to be null (or completely independent) if none of its pairs of distinct vertices are adjacent. In other words, all of its vertices are isolated. A null graph with \(n\) vertices is denoted by \(N_n\).
Example 13
- \(N_1\): 1 vertex, 0 edges
- \(N_2\): 2 vertices, 0 edges
- \(N_3\): 3 vertices, 0 edges
- \(N_4\): 4 vertices, 0 edges
- \(N_5\): 5 vertices, 0 edges
The first five null graphs are shown below.
Independent Set #
Let \(G\) be a graph and \(S \subseteq V(G)\) a subset of vertices. \(S\) is an independent set (or stable set) of \(G\) if \(G[S]\) is a null graph: no pair of vertices in \(S\) is adjacent.
Example 14
Let \(G\) be the graph of Example 12. The following subsets are independent sets of \(G\):
- \(S_1 = \{a, e, g\}\)
- \(S_2 = \{e, h\}\)
- \(S_3 = \{d, h, f\}\)
The figure shows \(G\) with the independent set \(S_1 = \{a, e, g\}\) highlighted: no pair of these vertices shares an edge.
If \(A\) is a clique in \(G\), then \(A\) is an independent set in the complement \(\bar{G}\), and vice versa. This follows directly from the definitions: the edges present in \(G[A]\) are absent from \(\bar{G}[A]\), turning a complete subgraph into a null subgraph.
Exercises #
The following exercises consolidate the concepts presented: neighborhood, complement, subgraphs, and independence.
Exercise 1: Neighborhood and special vertices
Statement:
Given the graph \(G = (V, E)\) with \(V = \{1, 2, 3, 4, 5\}\) and
$$E = \{(1,2),\ (1,3),\ (2,4),\ (3,4),\ (4,5)\}$$a) Compute \(N(v)\) for each vertex \(v \in V\).
b) Is there any isolated vertex? And any universal vertex?
Solution
a) Going through the edges for each vertex:
- \(N(1) = \{2, 3\}\)
- \(N(2) = \{1, 4\}\)
- \(N(3) = \{1, 4\}\)
- \(N(4) = \{2, 3, 5\}\)
- \(N(5) = \{4\}\)
b) No vertex has \(N(v) = \emptyset\), so there is no isolated vertex. No vertex has \(N(v) = V - \{v\}\) (for example, \(N(1) = \{2,3\} \neq \{2,3,4,5\}\)), so there is no universal vertex.
The graph \(G\) with all neighborhoods annotated:
Exercise 2: Complement graph
Statement:
Let \(G\) be the graph of Exercise 1. Determine \(\bar{G}\).
Solution
\(K_5\) has \(\binom{5}{2} = 10\) edges. Since \(|E(G)| = 5\), the complement has \(10 - 5 = 5\) edges, which are the pairs that do not appear in \(G\):
$$E(\bar{G}) = \{(1,4),\ (1,5),\ (2,3),\ (2,5),\ (3,5)\}$$\(G\) and \(\bar{G}\) side by side:
Exercise 3: Induced subgraph and independent set
Statement:
Let \(G\) be the graph of Exercise 1 and \(A = \{1, 2, 4\}\).
a) Determine the induced subgraph \(G[A]\).
b) Is \(S = \{1, 5\}\) an independent set of \(G\)? Justify.
Solution
a) \(V(G[A]) = \{1, 2, 4\}\). The edges of \(G\) with both endpoints in \(A\) are \((1,2)\) and \((2,4)\). Therefore:
$$E(G[A]) = \{(1,2),\ (2,4)\}$$b) Yes. The only pair in \(S\) is \(\{1, 5\}\), and \((1,5) \notin E(G)\). Hence \(G[S]\) is a null graph and \(S\) is an independent set.
On the left: \(G\) with \(A = \{1,2,4\}\) in orange and the edges of \(G[A]\) highlighted. On the right: \(S = \{1,5\}\) in green, with no edge between them.
Summary #
| Concept | Symbol/Notation | Description |
|---|---|---|
| Simple graph | \(G = (V, E)\) | Vertices + edges (unordered pairs) |
| Edge | \(e = (v, w)\) | Unordered pair; \(v\) and \(w\) are the endpoints |
| Endpoints of an edge | \(v, w\) | The two vertices that form the edge \((v, w)\) |
| Incidence | n/a | \(e = (v, w)\) is incident to the vertices \(v\) and \(w\) |
| Number of vertices | \(n\) | \(n = \lvert V(G) \rvert\) |
| Number of edges | \(m\) | \(m = \lvert E(G) \rvert\) |
| Neighborhood | \(N(v)\), \(N_G(v)\) | Set of neighbors of \(v\) in \(G\) |
| Isolated vertex | n/a | \(N(v) = \emptyset\) |
| Universal vertex | n/a | \(N(v) = V - \{v\}\) |
| Complement | \(\bar{G}\) | Same \(V\), complementary edges |
| Subgraph | \(H \subseteq G\) | \(V(H) \subseteq V(G)\) and \(E(H) \subseteq E(G)\) |
| Induced subgraph | \(G[A]\) | Vertices of \(A\) + all inherited edges |
| Spanning subgraph | n/a | \(V(H) = V(G)\), possibly fewer edges |
| Complete graph | \(K_n\) | Every pair adjacent; \(\binom{n}{2}\) edges |
| Null graph | \(N_n\) | No edges; all vertices isolated |
| Clique | n/a | \(A \subseteq V(G)\) with \(G[A]\) complete |
| Independent set | n/a | \(S \subseteq V(G)\) with \(G[S]\) null |
Next Steps #
With the vocabulary established (vertices, edges, neighborhood, subgraphs, and special graphs), we have the basis to start measuring local properties of each vertex. What is still missing is quantifying how many edges are incident to each vertex: this measure, called the degree, is the central object of the next article, where we will also prove the Handshaking Theorem, which relates the sum of the degrees to the number of edges of the graph.
