09 Introduction to Graph Theory

Graph structure and terminology

Graph theory studies relationships among objects. A graph is written as

where $V$ is a set of vertices and $E$ is a set of edges. For example, consider

This graph has four vertices and four edges. Vertices $a$ and $b$ are adjacent because the edge $ab$ joins them. The edge $ab$ is incident with both endpoints, $a$ and $b$.

The neighborhood of a vertex $v$, written $N(v)$, is the set of vertices adjacent to $v$. In this example,

Unless stated otherwise, introductory graph theory commonly uses simple undirected graphs:

• An undirected edge has no direction, so $uv$ and $vu$ represent the same edge.

• A simple graph has no loops and no repeated edges.

• A loop joins a vertex to itself.

• A multigraph may have multiple edges joining the same pair of vertices.

• A directed graph uses directed edges such as $(u,v)$.

• A weighted graph assigns a numerical value to each edge.

The order of a graph is $|V|$, and its size is $|E|$. An empty graph has no edges, while a trivial graph has one vertex and no edges.

The term graph refers to the complete structure of vertices and edges, while the term vertex refers to one of the individual objects in that structure.

Takeaway: A graph describes objects through vertices and relationships through edges; adjacency and incidence specify how those parts are connected.

Ways to represent a graph

Different representations emphasize different features of the same graph. For the graph with

the main representations are as follows.

• An edge list records the edges directly:

  $$(ab,ac,bc,cd).$$

• An adjacency list records the neighbors of each vertex. For example, the entries are $a\!:\!b,c$, $b\!:\!a,c$, $c\!:\!a,b,d$, and $d\!:\!c$.

• An adjacency matrix is a square matrix whose rows and columns correspond to vertices. For a simple undirected graph, an entry is $1$ when the corresponding vertices are adjacent and $0$ otherwise. In the order $(a,b,c,d)$,

  $$A=\begin{pmatrix} 0&1&1&0\\ 1&0&1&0\\ 1&1&0&1\\ 0&0&1&0 \end{pmatrix}.$$

  An undirected graph has a symmetric adjacency matrix, and a simple graph has zeros on the diagonal.

• An incidence matrix has rows for vertices and columns for edges. Its entry is $1$ when the vertex is an endpoint of the edge and $0$ otherwise. In a simple undirected graph, each column contains two entries equal to $1$.

A graph drawing is also a representation. Its exact geometric appearance is unimportant: moving vertices or bending edges does not change the graph as long as the same incidences are preserved.

For sparse graphs, meaning graphs with relatively few edges compared with the maximum possible number, adjacency lists are often more economical than adjacency matrices. Adjacency matrices, however, make adjacency tests direct and are useful in algebraic and computational settings.

Takeaway: Choose a representation according to the task: lists are convenient for enumerating connections, matrices support systematic tests, and drawings provide an immediate visual picture.

Degrees and the Handshaking Lemma

The degree of a vertex measures its local connectivity. In the example graph,

The degree sequence, usually listed in nonincreasing order, is therefore

A graph is regular when every vertex has the same degree. If every vertex has degree $r$, the graph is called $r$-regular.

The Handshaking Lemma provides a useful consistency check:

For this graph,

The factor of $2$ appears because every edge contributes one incidence at each of its two endpoints. Consequently, every finite undirected graph has an even number of odd-degree vertices.

A vertex with degree $0$ is isolated, so it has no neighbors. A vertex with degree $1$ is a leaf or pendant vertex. If loops are allowed, a loop contributes $2$ to the degree because it creates two endpoint incidences at the same vertex.

Takeaway: Degrees summarize local structure, while the Handshaking Lemma connects all local degree counts to the graph's total number of edges.

Walks, trails, paths, and cycles

Routes through a graph are classified by what they are allowed to repeat. A walk is a sequence of vertices

such that consecutive vertices are adjacent. Its length is $k$. Both vertices and edges may repeat. For example, $a,b,c,a,c$ is a walk of length $4$ in the example graph.

A trail is a walk that does not repeat an edge, although it may repeat vertices. The sequence $a,b,c,d$ is a trail.

A path is a walk that does not repeat vertices. For example, $a,c,d$ is a path of length $2$ from $a$ to $d$. The sequence $a,b,c,a$ is not a path because it repeats $a$.

A shortest path between two connected vertices has the smallest possible length. That length is the distance between the vertices, commonly written $d(u,v)$. The path graph $P_n$ has $n$ vertices and $n-1$ edges.

A cycle is a closed path: it starts and ends at the same vertex, with no other vertex repeated. In the example,

is a cycle of length $3$. The cycle graph $C_n$ has $n$ vertices and $n$ edges, and every vertex in it has degree $2$.

The distinctions can be organized as follows:

• A walk may repeat vertices and edges.

• A trail may repeat vertices but not edges.

• A path repeats neither vertices nor edges.

• A cycle is a closed path.

Takeaway: The restrictions become progressively stronger from walk to trail to path; cycles add the condition of returning to the starting vertex.

Connectivity and components

Connectivity describes whether vertices can reach one another. Two vertices are connected when there is a path between them. A graph is connected when every pair of vertices is connected.

The graph with edges $ab,ac,bc,cd$ is connected because, for example, $a,c,d$ is a path from $a$ to $d$. A graph that is not connected is disconnected, and its connected components are its maximal connected pieces.

For example, suppose

The connected components have vertex sets

An isolated vertex forms a component by itself. A graph is connected precisely when it has one connected component.

Connectivity does not require a unique route. There may be multiple paths between two vertices. In fact, two distinct paths between the same pair of vertices imply that the graph contains a cycle: following one path forward and the other backward produces a closed route with a repeated starting point.

A graph with no cycles is acyclic. A connected acyclic graph is called a tree.

Takeaway: Paths determine reachability, connected components partition a disconnected graph into maximal reachable regions, and cycles provide alternative routes.

Subgraphs and selected structure

A subgraph is a smaller graph contained within a larger graph. If $G=(V,E)$, then $H=(W,F)$ is a subgraph of $G$ when

and every edge in $F$ has both endpoints in $W$. A subgraph can be created by deleting vertices, deleting edges, or doing both.

For

choosing

defines a valid subgraph. The edge $cd$ cannot be included because $d\notin W$.

Two important special cases are:

• A spanning subgraph contains every vertex of the original graph but may contain only some of its edges. Thus, it has the form $H=(V,F)$ with $F\subseteq E$.

• An induced subgraph is determined by a chosen vertex set $W$. It contains every original edge whose endpoints are both in $W$, and is written $G[W]$.

For the example, the induced subgraph on $\{a,b,c\}$ contains all three edges $ab$, $ac$, and $bc$. A graph on the same three vertices that omits $ac$ is still a subgraph, but it is not the induced subgraph on that vertex set.

A connected component can be viewed as an induced subgraph consisting of one maximal set of mutually reachable vertices.

Takeaway: A general subgraph may omit selected vertices or edges, a spanning subgraph keeps all vertices, and an induced subgraph keeps every edge allowed by its selected vertices.

An integrated example

Consider the graph

Its order is $5$, and its size is $5$. The vertex degrees are

The degree sum verifies the Handshaking Lemma:

The sequence $1,2,3,1$ is a cycle of length $3$, while $1,3,4,5$ is a path from $1$ to $5$. The graph is connected because every vertex can be reached from every other vertex.

The vertices $1,2,3$, together with edges $12,23,31$, form a subgraph that is a cycle. The vertices $3,4,5$, together with edges $34,45$, form an induced path subgraph on those vertices.

This example shows how the concepts fit together:

• Degrees describe local connectivity.

• Paths describe routes between vertices.

• Cycles describe closed routes and alternative connections.

• Connectivity describes the graph as a whole.

• Subgraphs identify smaller structures inside the graph.

Final takeaway: To analyze a graph, first identify its vertices and edges, then examine representations and degrees, classify routes and cycles, determine connected components, and finally isolate relevant subgraphs.