# Chapter 3. Vertices and Edges # 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)\). If $$ 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. If $$ 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)\}. $$ If $$ 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. If $$ 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.