Introduction to Graph Theory

For all the definitions below, consider a graph $G$ with vertex set $V$ and edge set $E$.

Vertex

Denoted by a point.

Degree

The number of edges incident on a vertex. Denoted by $\text{deg}(v)$. A loop contributes 2 to the degree of a vertex.

Isolated Vertex

When a vertex’s degree is 0.

Pendant Vertex

When a vertex’s degree is 1.

Degree Sequence

The list of its vertex degrees sorted in non-increasing order.

Edge

Denoted by a line.

Loop

An edge that connects a vertex to itself.

Adjacency

Two vertices are said to be adjacent iff they are connected by an edge.

Two edges are said to be adjacent iff they share a common vertex.

Incidence

An edge is said to be incident to a vertex iff the vertex is one of the endpoints of the edge.

A vertex is said to be incident to an edge iff the edge is one of the edges connected to the vertex.

Subgraph

Suppose $G' = (V', E')$ and $G = (V, E)$.

If $V' \subseteq V$ and $E' \subseteq E$ then $G'$ is a subgraph of $G$.

Supergraph

In the above example, $G$ is a supergraph of $G'$.

Complement

Aka. inverse. For a simple graph $G$, its complement graph has:

• The same vertex set
• An edge between two vertices iff they are not adjacent in $G$.

Denoted by $G^c$.

Preliminary Definitions

Walk

A finite alternating sequence of vertices and edges, which begins and ends with a vertex, so that each edge is incident with the vertices preceding and following it, and any vertex or edge can appear more than once.

If $A$ is the adjacency matrix of $G$, entry (i, j) of Aᵐ = number of walks of length m from vᵢ to vⱼ

Explanation: Matrix multiplication accumulates all possible paths step by step.

Trail

A walk with no repeating edges. Vertices may repeat.

Circuit

Aka. closed trail. A trial with the same starting and ending vertices. No repeating edges.

Path

A trail with no repeating vertices (except the starting and ending pair). No repeating edges.

In a connected graph with $n$ vertices, any two vertices are connected by a path of length $\le n − 1$.

Cycle

A closed path. Starts and ends in the same vertex. No repeating vertices and no repeating edges.

All cycles with the same number of vertices, edges, are considered a single cycle, even if written in a different order.

Euler Path

A trail that traverses every edge. No repeating edges.

Euler Circuit

A closed Euler path. Starts and ends in the same vertex.

Hamiltonian Path

Aka. traceable path. A path that contains every vertex of the graph. No repeating edges and no repeating vertices.

Hamiltonian Cycle

Aka. Hamiltonian Circuit. A closed Hamiltonian path.

Comparison

*must traverse every edge. **must traverse every vertex.