Chapter 3. Vertices and Edges

A graph is built from two kinds of objects: vertices and edges. Vertices are the objects being related. Edges are the relations between them. In a simple undirected graph, an edge is an unordered pair of distinct vertices; in a directed graph, an edge is an ordered pair. This distinction is standard in elementary graph theory.

3.1 Vertices

A vertex is an element of the vertex set $V(G)$ .

G = (V,E),

then each element of $V$ is a vertex of $G$ . Vertices may be written as

u, v, w

or as indexed symbols such as

v_1, v_2, \ldots, v_n.

The number of vertices in a graph is its order:

|V(G)|.

Vertices are sometimes called nodes, especially in computer science. In this book, the word vertex is used for the mathematical object. A vertex may have a label, but the label is only a name. The structure of the graph comes from adjacency, not from the spelling of the labels.

3.2 Edges

An edge is a connection between vertices.

In a simple undirected graph, an edge joining $u$ and $v$ is written as

\{u,v\}.

The order of the endpoints does not matter:

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

Thus an undirected edge records a symmetric connection.

e = \{u,v\},

then $u$ and $v$ are called the endpoints of $e$ . The edge $e$ is said to join $u$ and $v$ .

The number of edges in a graph is its size:

|E(G)|.

3.3 The Incidence Relation

Incidence is the relation between vertices and edges.

An edge $e$ is incident with a vertex $v$ if $v$ is one of the endpoints of $e$ . If

e = \{u,v\},

then $e$ is incident with $u$ and incident with $v$ .

The terms adjacency and incidence should be kept separate.

Term	Objects related	Meaning
Adjacent	vertex and vertex	Two vertices share an edge
Incident	vertex and edge	The vertex is an endpoint of the edge
Endpoint	vertex of an edge	A vertex used by an edge

For example, if

e = \{a,b\},

then $a$ and $b$ are adjacent, while $e$ is incident with $a$ and with $b$ .

3.4 Adjacent Vertices

Two vertices are adjacent if an edge joins them.

In an undirected graph $G$ , vertices $u$ and $v$ are adjacent when

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

Adjacent vertices are also called neighbors.

The set of all neighbors of a vertex $v$ is called its neighborhood and is written as

N(v).

For a simple graph,

N(v) = \{u \in V(G) : \{u,v\} \in E(G)\}.

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

and

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

then

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

N(b) = \{a\},

N(c) = \{a,d\},

and

N(d) = \{c\}.

3.5 The Degree of a Vertex

The degree of a vertex is the number of edges incident with it.

The degree of $v$ is written as

\deg(v).

In a simple graph, the degree is the number of neighbors:

\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.

Degree measures local connectivity. It tells how many immediate connections a vertex has, but it does not determine the whole position of the vertex in the graph.

3.6 Maximum and Minimum Degree

The maximum degree of a graph $G$ is the largest degree among its vertices. It is written as

\Delta(G).

The minimum degree of $G$ is the smallest degree among its vertices. It is written as

\delta(G).

Thus

\Delta(G) = \max_{v \in V(G)} \deg(v)

and

\delta(G) = \min_{v \in V(G)} \deg(v).

For a graph with degree sequence

(4,3,3,2,1,1),

we have

\Delta(G)=4

and

\delta(G)=1.

These quantities give coarse information about the graph. They do not describe the full graph, but they are often enough to state useful bounds.

3.7 Edge Endpoints

In a simple graph, every edge has exactly two distinct endpoints.

e = \{u,v\},

then

u \ne v.

This excludes loops. It also means that every edge contributes one incidence to each of two different vertices.

In a multigraph or pseudograph, this convention may change. A loop has the same vertex as both endpoints. Multiple edges may share the same endpoint pair. Since conventions differ across books, one must always check what class of graph is being used.

3.8 Loops

A loop is an edge whose two endpoints are the same vertex.

A loop at $v$ may be written as

\{v,v\}.

Simple graphs exclude loops. Pseudographs allow loops. Some multigraph conventions allow loops, while others allow multiple edges but still exclude loops.

In an undirected graph, a loop contributes $2$ to the degree of its vertex. This is because the loop has two ends, and both ends are incident with the same vertex.

For example, if $v$ has one ordinary edge incident with it and one loop at it, then

\deg(v) = 3.

The ordinary edge contributes $1$ . The loop contributes $2$ .

3.9 Multiple Edges

Two edges are parallel if they have the same endpoints.

A graph that allows parallel edges is called a multigraph.

For example, suppose two vertices $a$ and $b$ are joined by three distinct edges:

e_1, e_2, e_3.

Each edge has endpoint pair $\{a,b\}$ , but the edges are separate objects.

This distinction matters in applications. If vertices are cities and edges are roads, then two cities may be connected by several roads. A simple graph would record only whether a connection exists. A multigraph can record each road separately.

3.10 Directed Edges

In a directed graph, an edge has direction.

A directed edge from $u$ to $v$ is written as

(u,v).

The first vertex is the tail. The second vertex is the head.

Thus, for the arc

(u,v),

the tail is $u$ , and the head is $v$ .

Unlike undirected edges,

(u,v) \ne (v,u)

in general.

Directed edges model one-way relations: links, citations, dependencies, transitions, control flow, and precedence constraints.

3.11 In-Neighbors and Out-Neighbors

In a directed graph, a vertex has two kinds of neighbors.

The out-neighborhood of $v$ is the set of vertices reached by arcs leaving $v$ :

N^+(v) = \{u \in V(G) : (v,u) \in E(G)\}.

The in-neighborhood of $v$ is the set of vertices with arcs entering $v$ :

N^-(v) = \{u \in V(G) : (u,v) \in E(G)\}.

The corresponding degrees are

\deg^+(v)=|N^+(v)|

and

\deg^-(v)=|N^-(v)|

when the directed graph has no parallel arcs.

For example, if

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

then

N^+(a)=\{b,c\}

and

N^-(a)=\{c,d\}.

Thus

\deg^+(a)=2

and

\deg^-(a)=2.

3.12 Edge Sets as Data

In finite graph theory, an edge set is often written explicitly.

For example,

V = \{1,2,3,4,5\}

and

E = \{\{1,2\}, \{1,3\}, \{2,4\}, \{4,5\}\}.

This is enough to define the graph completely.

From the edge set, one can recover adjacency, incidence, degree, neighborhoods, paths, and components. In a finite simple graph, the edge set is the complete structural record of the graph once the vertex set is fixed.

3.13 Vertex Labels and Structure

Vertex labels identify vertices, but they do not determine graph structure.

Consider the graph

V_1 = \{a,b,c\}, \qquad E_1 = \{\{a,b\}, \{b,c\}\}.

Now consider

V_2 = \{1,2,3\}, \qquad E_2 = \{\{1,2\}, \{2,3\}\}.

These graphs have different labels, but the same structure. Each is a path on three vertices.

Graph theory usually studies structure up to relabeling. This idea is formalized by graph isomorphism.

3.14 Edge Labels and Weights

Edges may carry additional information.

A weighted edge has a numerical value. A labeled edge has a name, type, or category.

For example, in a transportation graph, an edge may have a distance:

w(\{u,v\}) = 12.5.

In a knowledge graph, an edge may have a relation label:

\text{born\_in}(p,c).

The unweighted graph records only adjacency. The weighted or labeled graph records additional data attached to the connection.

It is useful to separate the underlying graph from the data stored on it. The underlying graph tells which vertices are connected. The labels and weights describe the kind or cost of each connection.

3.15 Complete and Empty Edge Sets

For a simple graph on $n$ vertices, the largest possible edge set contains one edge for every pair of distinct vertices.

This gives the complete graph $K_n$ . Its edge set has size

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

A complete graph is therefore the graph with maximum possible adjacency among $n$ vertices.

At the other extreme is the empty graph on $n$ vertices, whose edge set is

E = \varnothing.

In the empty graph, every vertex has degree $0$ . In the complete graph $K_n$ , every vertex has degree $n-1$ .

3.16 The Handshaking Principle

Because every edge in a finite undirected graph has two endpoints, the total degree count is twice the number of edges:

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

This identity is called the degree sum formula or the handshaking lemma. It implies that the number of vertices of odd degree is even.

The formula is a basic example of double counting. Count incidences between vertices and edges in two ways. Counting by edges gives $2|E(G)|$ . Counting by vertices gives the sum of the degrees.

3.17 Example

Let

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

and

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

The order is

|V| = 5.

The size is

|E| = 5.

The neighborhoods are

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

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

N(c)=\{a,b,d\},

N(d)=\{c,e\},

N(e)=\{d\}.

The degrees are

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

The degree sum is

2+2+3+2+1 = 10.

Since

2|E| = 2 \cdot 5 = 10,

the handshaking lemma holds.

3.18 Summary

Vertices are the objects of a graph. Edges are the connections between them. An edge has endpoints. An edge is incident with its endpoints. Two vertices are adjacent when an edge joins them.

The local structure around a vertex is described by its neighborhood and degree. In directed graphs, edges have tails and heads, so neighborhoods and degrees split into incoming and outgoing versions.

The edge set determines the adjacency structure of a finite graph. By studying how vertices and edges interact, graph theory builds the language needed for paths, cycles, connectivity, trees, colorings, matchings, flows, and graph algorithms.