# Chapter 2. Basic Definitions

# Chapter 2. Basic Definitions

Graph theory begins with a small vocabulary. The terms are simple, but they must be used precisely. Most later theorems depend on exact distinctions among vertices, edges, adjacency, incidence, degree, paths, cycles, and subgraphs.

## 2.1 Graph

A **graph** is an ordered pair

$$
G = (V,E),
$$

where \(V\) is a set of vertices and \(E\) is a set of edges.

The set \(V\) is called the **vertex set** of \(G\). The set \(E\) is called the **edge set** of \(G\). When needed, they are written as

$$
V(G)
$$

and

$$
E(G).
$$

A graph records relationships among elements of \(V\). Each edge represents one such relationship.

For example, let

$$
V = \{a,b,c,d\}
$$

and

$$
E = \{\{a,b\}, \{a,c\}, \{b,d\}\}.
$$

Then

$$
G = (V,E)
$$

is a graph with four vertices and three edges.

## 2.2 Vertex

A **vertex** is a basic object of a graph.

Vertices are also called **nodes**, especially in computer science and network applications. In this book, the word vertex is used for the mathematical object. The word node may appear when discussing algorithms, data structures, or networks.

A vertex may have a label, such as \(a\), \(b\), \(1\), \(2\), or \(v_3\). The label names the vertex. It does not determine its mathematical role.

Two graphs may have different vertex labels but the same structure. This point becomes important in the study of graph isomorphism.

## 2.3 Edge

An **edge** is a connection between vertices.

In an undirected graph, an edge joining \(u\) and \(v\) is written as

$$
\{u,v\}.
$$

The order does not matter:

$$
\{u,v\} = \{v,u\}.
$$

In a directed graph, an edge from \(u\) to \(v\) is written as

$$
(u,v).
$$

Here the order matters. The edge \((u,v)\) begins at \(u\) and ends at \(v\).

Undirected edges express symmetric relations. Directed edges express ordered or one-way relations.

## 2.4 Order and Size

The **order** of a graph is the number of vertices.

If \(G = (V,E)\), then the order of \(G\) is

$$
|V|.
$$

The **size** of a graph is the number of edges:

$$
|E|.
$$

For example, if

$$
V = \{a,b,c,d,e\}
$$

and

$$
E = \{\{a,b\}, \{b,c\}, \{c,d\}\},
$$

then the graph has order \(5\) and size \(3\).

Order measures how many objects the graph contains. Size measures how many connections it contains.

## 2.5 Adjacent Vertices

Two vertices are **adjacent** if there is an edge between them.

In an undirected graph, \(u\) and \(v\) are adjacent when

$$
\{u,v\} \in E(G).
$$

The vertices \(u\) and \(v\) are then called **neighbors**.

The set of all neighbors of \(v\) is called the **neighborhood** of \(v\). It is often written as

$$
N(v).
$$

For example, if

$$
E = \{\{a,b\}, \{a,c\}, \{c,d\}\},
$$

then

$$
N(a) = \{b,c\}.
$$

## 2.6 Incidence

An edge is **incident** with a vertex if the vertex is one of its endpoints.

If

$$
e = \{u,v\},
$$

then \(e\) is incident with \(u\) and with \(v\).

The vertices \(u\) and \(v\) are called the **endpoints** of \(e\).

Adjacency is a relation between vertices. Incidence is a relation between a vertex and an edge.

| Term | Relation |
|---|---|
| Adjacent | vertex to vertex |
| Incident | vertex to edge |
| Endpoint | vertex belonging to an edge |

## 2.7 Degree

The **degree** of a vertex in an undirected graph is the number of edges incident with it.

The degree of \(v\) is written as

$$
\deg(v).
$$

For a simple graph, this is the same as the number of neighbors of \(v\):

$$
\deg(v) = |N(v)|.
$$

For example, let

$$
E = \{\{a,b\}, \{a,c\}, \{a,d\}, \{b,d\}\}.
$$

Then

$$
\deg(a) = 3,
\qquad
\deg(b) = 2,
\qquad
\deg(c) = 1,
\qquad
\deg(d) = 2.
$$

A vertex of degree \(0\) is called an **isolated vertex**. A vertex of degree \(1\) is called a **leaf** or **pendant vertex**.

## 2.8 The Handshaking Lemma

In every finite undirected graph, the sum of all vertex degrees equals twice the number of edges:

$$
\sum_{v \in V(G)} \deg(v) = 2|E(G)|.
$$

Each edge has two endpoints. Therefore each edge contributes \(2\) to the total degree count.

This result is called the **handshaking lemma**. It is one of the first counting principles in graph theory.

A direct consequence is that the number of vertices of odd degree is even. Since the total degree sum is even, an odd number of odd summands cannot occur.

## 2.9 Loop

A **loop** is an edge that joins a vertex to itself.

A loop at \(v\) is written as

$$
\{v,v\}
$$

in an undirected setting, or as

$$
(v,v)
$$

in a directed setting.

Simple graphs do not allow loops. Multigraphs may allow them.

A loop contributes \(2\) to the degree of its vertex in an undirected graph, because both endpoints are the same vertex but the edge still has two ends.

## 2.10 Multiple Edges

Two or more edges are **parallel** or **multiple edges** if they join the same pair of vertices.

A simple graph has at most one edge between any two distinct vertices. A multigraph allows multiple edges.

For example, if two cities are connected by several different roads, then a multigraph may represent each road as a separate edge.

| Graph type | Loops allowed | Multiple edges allowed |
|---|---:|---:|
| Simple graph | No | No |
| Multigraph | Usually yes or sometimes no, depending on convention | Yes |
| Pseudograph | Yes | Yes |
| Directed graph | Depends on convention | Depends on convention |

Conventions vary. A reference text should state its convention before proving results.

## 2.11 Simple Graph

A **simple graph** is an undirected graph with no loops and no multiple edges.

In a simple graph, every edge is a two-element subset of the vertex set. Thus an edge has the form

$$
\{u,v\}
$$

where

$$
u \ne v.
$$

Most introductory graph theory begins with simple graphs because they expose the core ideas without additional technical cases.

Unless otherwise stated, the word graph in many chapters of this book means finite simple undirected graph.

## 2.12 Complete Graph

A **complete graph** is a simple graph in which every pair of distinct vertices is adjacent.

The complete graph on \(n\) vertices is denoted by

$$
K_n.
$$

Its number of edges is

$$
\binom{n}{2} = \frac{n(n-1)}{2}.
$$

For example, \(K_1\) has one vertex and no edges. \(K_2\) has two vertices and one edge. \(K_3\) is a triangle. \(K_4\) has four vertices and six edges.

Complete graphs often serve as extremal examples because they contain the largest possible number of edges for a simple graph of fixed order.

## 2.13 Empty and Null Graphs

An **empty graph** is a graph with vertices but no edges.

If

$$
V = \{v_1,\ldots,v_n\}
$$

and

$$
E = \varnothing,
$$

then the graph has order \(n\) and size \(0\).

Some authors use the term **null graph** for a graph with no vertices. Other authors use it for a graph with vertices and no edges. To avoid ambiguity, this book uses:

| Term | Meaning |
|---|---|
| Empty graph | Vertices, no edges |
| Null graph | No vertices, no edges |

## 2.14 Directed Graph

A **directed graph**, or **digraph**, is a graph whose edges have directions.

A directed graph is written as

$$
D = (V,A),
$$

where \(V\) is the vertex set and \(A\) is the set of arcs.

An arc from \(u\) to \(v\) is written as

$$
(u,v).
$$

The vertex \(u\) is the **tail** of the arc. The vertex \(v\) is the **head** of the arc.

In a directed graph, \((u,v)\) and \((v,u)\) are different arcs.

## 2.15 In-Degree and Out-Degree

In a directed graph, the **out-degree** of a vertex is the number of arcs leaving it. The **in-degree** is the number of arcs entering it.

These are written as

$$
\deg^+(v)
$$

and

$$
\deg^-(v).
$$

For example, if

$$
A = \{(a,b), (a,c), (c,a), (d,a)\},
$$

then

$$
\deg^+(a) = 2,
\qquad
\deg^-(a) = 2.
$$

The directed version of the handshaking lemma says

$$
\sum_{v \in V} \deg^+(v) =
\sum_{v \in V} \deg^-(v) =
|A|.
$$

Each arc leaves exactly one vertex and enters exactly one vertex.

## 2.16 Weighted Graph

A **weighted graph** is a graph in which each edge has an associated value called a weight.

A weight may represent distance, cost, capacity, time, probability, similarity, or resistance.

If \(w\) is a weight function, then

$$
w(e)
$$

denotes the weight of edge \(e\).

For example, in a road network, vertices may be cities and edge weights may be distances between cities.

Weighted graphs are essential in shortest path problems, minimum spanning trees, network flow, optimization, and many applications.

## 2.17 Labeled Graph

A **labeled graph** is a graph whose vertices or edges carry labels.

A vertex label may be a name, identifier, type, coordinate, or record. An edge label may represent a relation type, timestamp, direction, cost, or category.

Labels are part of the data model. Two graphs may have the same adjacency pattern but different labels.

In pure graph theory, labels are often ignored unless explicitly needed. In applications, labels usually carry important semantic information.

## 2.18 Finite and Infinite Graphs

A graph is **finite** if its vertex set and edge set are finite.

A graph is **infinite** if its vertex set or edge set is infinite.

Most algorithmic graph theory concerns finite graphs. Infinite graphs appear in logic, topology, group theory, model theory, and the study of infinite networks.

In this book, graphs are finite unless otherwise stated.

## 2.19 Subgraph

A **subgraph** of a graph \(G\) is a graph formed from some vertices and some edges of \(G\).

If

$$
G = (V,E),
$$

then

$$
H = (V_H,E_H)
$$

is a subgraph of \(G\) when

$$
V_H \subseteq V
$$

and

$$
E_H \subseteq E.
$$

Every edge in \(E_H\) must have both endpoints in \(V_H\).

Subgraphs allow one to study parts of a graph. A path, a cycle, a component, and a tree inside a graph are all examples of subgraphs.

## 2.20 Induced Subgraph

An **induced subgraph** is formed by choosing vertices and keeping all edges among them that appear in the original graph.

If \(S \subseteq V(G)\), then the subgraph induced by \(S\) is written as

$$
G[S].
$$

Its vertex set is \(S\). Its edge set contains every edge of \(G\) whose endpoints both lie in \(S\).

Thus an induced subgraph is determined completely by its chosen vertex set.

This differs from an arbitrary subgraph, where one may choose to keep or discard edges.

## 2.21 Spanning Subgraph

A **spanning subgraph** is a subgraph that contains all vertices of the original graph.

If \(H\) is a spanning subgraph of \(G\), then

$$
V(H) = V(G).
$$

The edge set \(E(H)\) may be smaller than \(E(G)\).

A spanning tree is an important example. It contains all vertices of a connected graph and enough edges to connect them without cycles.

## 2.22 Complement

The **complement** of a simple graph \(G\) is the graph \(\overline{G}\) with the same vertex set, where two distinct vertices are adjacent in \(\overline{G}\) exactly when they are not adjacent in \(G\).

Thus,

$$
V(\overline{G}) = V(G).
$$

For distinct vertices \(u\) and \(v\),

$$
\{u,v\} \in E(\overline{G})
$$

exactly when

$$
\{u,v\} \notin E(G).
$$

The complement exchanges edges and non-edges.

If \(G\) has \(n\) vertices and \(m\) edges, then

$$
\overline{G}
$$

has

$$
\binom{n}{2} - m
$$

edges.

## 2.23 Isomorphism

Two graphs are **isomorphic** if they have the same structure after relabeling vertices.

Graphs \(G\) and \(H\) are isomorphic if there exists a bijection

$$
f : V(G) \to V(H)
$$

such that for all vertices \(u,v \in V(G)\),

$$
\{u,v\} \in E(G)
$$

if and only if

$$
\{f(u),f(v)\} \in E(H).
$$

The function \(f\) is called an isomorphism.

Isomorphic graphs have the same order, size, degree sequence, number of components, number of cycles of each length, and other structural properties. Different drawings or different vertex names do not change the graph structure.

## 2.24 Degree Sequence

The **degree sequence** of a finite graph is the list of vertex degrees, usually written in nonincreasing order.

For example, if the degrees are

$$
3,1,2,2,
$$

then the degree sequence is

$$
(3,2,2,1).
$$

The degree sequence is a graph invariant. Isomorphic graphs have the same degree sequence.

The converse is not always true. Two non-isomorphic graphs may have the same degree sequence.

## 2.25 Summary

The basic language of graph theory consists of vertices, edges, adjacency, incidence, degree, subgraphs, complements, and isomorphisms.

A graph has order \(|V|\) and size \(|E|\). In an undirected graph, degree counts incident edges. In a directed graph, in-degree and out-degree count entering and leaving arcs. Simple graphs exclude loops and multiple edges. Multigraphs and directed graphs extend the basic model.

These definitions form the grammar of graph theory. Later chapters use them to define paths, cycles, connectedness, trees, colorings, matchings, flows, and spectra.