Graph Basics

Definition

A graph $G = (V, E)$ consists of:

• $V$: a set of vertices (nodes)
• $E$: a set of edges (connections between vertices)

Types of Graphs

Undirected Graph

Edges have no direction: $\{u, v\}$ connects $u$ and $v$ symmetrically.

Directed Graph (Digraph)

Edges have direction: $(u, v)$ goes from $u$ to $v$.

Simple Graph

• No loops (edges from vertex to itself)
• No multiple edges between same vertices

Multigraph

Multiple edges between vertices allowed.

Pseudograph

Loops and multiple edges allowed.

Weighted Graph

Each edge has an associated numerical value (weight).

Basic Terminology

Vertices

Term	Definition
Adjacent	Two vertices connected by an edge
Neighbor	A vertex adjacent to $v$
Degree $d(v)$	Number of edges incident to $v$
Isolated vertex	Vertex with degree 0
Pendant vertex	Vertex with degree 1

Edges

Term	Definition
Incident	Edge $e$ is incident to vertices it connects
Loop	Edge connecting vertex to itself
Multiple edges	Two or more edges between same vertices

Degree

Undirected Graphs

$d(v) = \text{number of edges incident to } v$

(Loops count twice)

Handshaking Lemma

$\sum_{v \in V} d(v) = 2|E|$

Each edge contributes 2 to the total degree.

Corollary: The number of vertices with odd degree is even.

Directed Graphs

• In-degree $d^-(v)$: edges coming into $v$
• Out-degree $d^+(v)$: edges going out of $v$

$\sum_{v \in V} d^-(v) = \sum_{v \in V} d^+(v) = |E|$

Graph Representations

Adjacency List

For each vertex, list its neighbors.

Example: Triangle (vertices 1, 2, 3)

1: [2, 3]
2: [1, 3]
3: [1, 2]

Space: $O(|V| + |E|)$

Adjacency Matrix

$A[i][j] = 1$ if edge between $i$ and $j$, else 0.

Example: Triangle $A = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}$

Space: $O(|V|^2)$

Incidence Matrix

Rows = vertices, Columns = edges. $M[v][e] = 1$ if $v$ is incident to $e$.

Special Graphs

Complete Graph $K_n$

Every pair of vertices is connected.

• Vertices: $n$
• Edges: $\binom{n}{2} = \frac{n(n-1)}{2}$
• Each vertex has degree $n - 1$

Complete Bipartite Graph $K_{m,n}$

Vertices split into two groups of size $m$ and $n$. Every vertex in one group connected to every vertex in the other.

• Edges: $m \times n$

Cycle $C_n$

$n$ vertices in a cycle. Each vertex has degree 2.

Path $P_n$

$n$ vertices in a line. Two endpoints have degree 1, others have degree 2.

Wheel $W_n$

Cycle $C_n$ plus a central hub connected to all cycle vertices.

• Vertices: $n + 1$
• Edges: $2n$

n-Cube $Q_n$

Vertices are $n$-bit binary strings. Edge between two vertices if they differ in exactly one bit.

• Vertices: $2^n$
• Edges: $n \cdot 2^{n-1}$
• Regular with degree $n$

Subgraphs

$H = (V', E')$ is a subgraph of $G = (V, E)$ if:

• $V' \subseteq V$
• $E' \subseteq E$
• All edges in $E'$ have endpoints in $V'$

Induced Subgraph

Given $V' \subseteq V$, the induced subgraph $G[V']$ includes all edges of $G$ with both endpoints in $V'$.

Spanning Subgraph

A subgraph that includes all vertices of $G$.

Graph Operations

Union

$G_1 \cup G_2 = (V_1 \cup V_2, E_1 \cup E_2)$

Complement

$\overline{G}$ has the same vertices as $G$, with edge $(u, v)$ iff $(u, v)$ is NOT in $G$.

For simple graphs: $|E(G)| + |E(\overline{G})| = \binom{n}{2}$

Contraction

Remove an edge $(u, v)$ and merge $u$ and $v$ into a single vertex.