Graphs, Isomorphism & Connectivity

We formally define graphs, their basic properties (degree, subgraphs, complement), and the crucial concept of graph isomorphism. The Handshake Theorem connects vertex degrees to edge counts. We also introduce connectivity, components, and directed graphs (digraphs).

Learning Objectives

Define graphs, multigraphs, and simple graphs formally

Compute vertex degrees and apply the Handshake Theorem

Determine whether two graphs are isomorphic or prove they are not

Identify connected components and understand connectivity

Define directed graphs, in-degree, and out-degree

Key Concepts

Graph Basics

A graph $G = (V, E)$ consists of a vertex set $V$ and an edge set $E$ , where each edge connects two vertices. A simple graph has no loops or multiple edges. The degree $d(v)$ of a vertex $v$ is the number of edges incident to it.

Important graph families: complete graph $K_n$ , path $P_n$ , cycle $C_n$ , complete bipartite $K_{m,n}$ , Petersen graph.

-
$K_n$ has $\binom{n}{2}$ edges and every vertex has degree $n-1$
-
A graph has an even number of odd-degree vertices (corollary of Handshake Theorem)
-
Subgraph: $H \subseteq G$ if $V(H) \subseteq V(G)$ and $E(H) \subseteq E(G)$
-
$|E(G)| + |E(\overline{G})| = \binom{n}{2}$

Graph Isomorphism

Two graphs $G$ and $H$ are isomorphic ( $G \cong H$ ) if there exists a bijection $\phi: V(G) \to V(H)$ that preserves adjacency: $uv \in E(G) \iff \phi(u)\phi(v) \in E(H)$ .

To prove isomorphism, exhibit the bijection. To disprove it, find an invariant that differs (number of vertices, edges, degree sequence, connectivity, girth, etc.).

-
Isomorphism invariants: $|V|$ , $|E|$ , degree sequence, connectivity, girth, chromatic number
-
If any invariant differs, the graphs are NOT isomorphic
-
Matching invariants does NOT prove isomorphism — you must exhibit the bijection
-
Self-complementary graphs: $G \cong \overline{G}$ (requires $|E| = \binom{n}{2}/2$ )

Connectivity

A graph is connected if there is a path between every pair of vertices. Otherwise it decomposes into connected components. The number of components is denoted $c(G)$ .

A cut vertex is a vertex whose removal increases the number of components. A bridge is an edge whose removal increases components.

-
A connected graph on $n$ vertices has at least $n-1$ edges
-
A tree is a connected graph with exactly $n-1$ edges
-
Removing a bridge increases components by exactly 1

Directed Graphs

A directed graph (digraph) $G = (V, E)$ has edges that are ordered pairs. The in-degree $d^-(v)$ is the number of edges coming into $v$ ; the out-degree $d^+(v)$ is the number of edges going out of $v$ .

For any digraph: $\sum_v d^+(v) = \sum_v d^-(v) = |E|$ .

-
$\sum_v d^+(v) = \sum_v d^-(v) = |E|$
-
Edges $(u,v)$ and $(v,u)$ are distinct in a digraph (unlike undirected graphs)
-
Directed graphs are used for flow networks, DFS edge classification, and topological ordering

W1: Permutations, Combinations & Binomial Theorem W3: Trees & BFS