Introduction to graphs and graph isomorphism

Graph theory is the last big block of the final. This week you learn the language: vertices, edges, degree, special graphs, and when two graphs are “the same” (isomorphism). Next week, paths, Euler and Hamilton questions will come in this language. It is not on the midterm, it is a final exam topic. The exam questions are short and computational: “How many edges?”, “Is it bipartite?”, “Are these graphs isomorphic?”.

Golden rules:

1. Handshaking theorem: the sum of the degrees is twice the number of edges.
2. So the number of odd-degree vertices is even.
3. Bipartite $\iff$ no odd cycle $\iff$ 2-colorable.
4. To say not isomorphic, it is enough for a single invariant to differ. To show they are isomorphic, you must write the mapping.

Basic definitions

A graph $G = (V, E)$: a set of vertices $V$ and a set of edges $E$, each connecting one or two vertices.

Two vertices with an edge between them are adjacent. The degree $\deg(v)$ of a vertex is the number of edges touching it; a loop adds 2 to the degree. A vertex of degree 0 is isolated, one of degree 1 is pendant.

Intuition: vertices are teammates, edges are “having passed to each other”. The degree is the number of different people a player exchanges passes with.

The handshaking theorem

$2m = \sum_{v\in V} \deg(v), \qquad m = |E|.$

Every edge has two ends, and each end adds 1 to the degree of a vertex. In directed graphs the in-degree $\deg^-(v)$ and out-degree $\deg^+(v)$ are separate: $\sum \deg^-(v) = \sum \deg^+(v) = m$.

Example. $V = \{a,b,c,d,e\}$, $E = \{ab, ac, bc, cd, de\}$:

deg(a) = 2  (b, c)
deg(b) = 2  (a, c)
deg(c) = 3  (a, b, d)
deg(d) = 2  (c, e)
deg(e) = 1  (d)      -> pendant
total = 10 = 2 * 5 edges
odd-degree vertices: c, e  -> 2 of them (even)

A fully written proof

Theorem. An undirected graph has an even number of vertices of odd degree.

Proof. Let $V_1$ be the set of vertices of even degree and $V_2$ the set of vertices of odd degree in $G = (V,E)$ with $m$ edges. By the handshaking theorem, $2m = \sum_{v\in V_1}\deg(v) + \sum_{v\in V_2}\deg(v).$ The left side is even. The first sum on the right is even, since each of its terms is even. Hence the second sum is the difference of two even numbers, so it is even. Every term of the second sum is odd, and a sum of odd numbers is even only if the number of terms is even. Therefore $|V_2|$ is even. $\blacksquare$

In plain words: split the total into even and odd parts, remove the even part, and what remains, a sum of odd numbers, must be even. That happens only with an even number of odd terms. On the exam you use this theorem in a question like “Is there a graph with degrees 3, 3, 2, 1, 1, 1?”: there are 5 odd-degree vertices, impossible.

PITFALL · Thinking a graph exists because the sum is even. The sum of the sequence $3,3,3,1$ is 10, even. But in a simple graph with 4 vertices, degree 3 means “connected to everyone”, and then the last vertex would also have degree 3. An even sum is a necessary condition, not sufficient.

Special graphs

A graph whose degrees are all equal is called regular: $K_n$, $C_n$, $Q_n$ are regular; $W_n$ ($n \neq 3$) is not.

Check: $K_5$ has 10 edges, $Q_3$ has 12 edges, $W_4$ has 5 vertices and 8 edges.

Bipartite graphs

If $V$ can be split into two disjoint sets $V_1, V_2$ and every edge connects a vertex in $V_1$ to a vertex in $V_2$, the graph is bipartite. Equivalent definition: you can color the vertices with two colors so that neighbors have different colors.

Theorem: A graph is bipartite if and only if it contains no cycle of odd length.

Practical test: make one vertex red, its neighbors blue, their neighbors red… If two neighbors of the same color appear, it is not bipartite.

C6:  1R 2B 3R 4B 5R 6B, edge 6-1 is B-R   -> bipartite
C5:  1R 2B 3R 4B 5R, edge 5-1 is R-R      -> NOT bipartite
K3:  triangle = cycle of length 3          -> NOT bipartite

Representing a graph

Adjacency list: the neighbors of each vertex. Efficient for sparse graphs.

Adjacency matrix $A$: $a_{ij} = 1$ if the edge $v_i v_j$ exists, otherwise 0. The example graph above (in the order $a,b,c,d,e$):

$A = \begin{bmatrix} 0&1&1&0&0\\ 1&0&1&0&0\\ 1&1&0&1&0\\ 0&0&1&0&1\\ 0&0&0&1&0 \end{bmatrix}$

For an undirected graph $A$ is symmetric; for a simple graph the diagonal is 0 and the row sum gives the degree. In a multigraph $a_{ij}$ is the number of parallel edges. The incidence matrix is a vertex × edge table: $m_{ij} = 1$ if the edge $e_j$ touches $v_i$.

Subgraph: a graph made of subsets of $V$ and $E$. Complement $\overline{G}$: the same vertices, all the edges that are not in $G$. $m(G) + m(\overline{G}) = \frac{n(n-1)}{2}$.

Graph isomorphism

$G_1 = (V_1,E_1)$ and $G_2 = (V_2,E_2)$ are isomorphic if there is a one-to-one and onto $f: V_1\to V_2$ such that

$uv \in E_1 \iff f(u)f(v)\in E_2.$

Intuition: the same graph, with the vertices named differently and drawn differently on paper.

Showing not isomorphic: invariants

A graph invariant is a property preserved by isomorphism. If one differs, the graphs cannot be isomorphic.

Example. $C_6$ and two disjoint triangles ($2K_3$). Both have 6 vertices, 6 edges, all degrees 2. But $C_6$ is connected and has no triangle; $2K_3$ has two components and contains triangles. Not isomorphic.

Showing isomorphic

All invariants being the same is not a proof. You must write the mapping and check every edge. Method:

1. Check that the degree sequences are the same.
2. Start with vertices of unique degree (degree 3 → degree 3).
3. Preserve adjacencies: the neighbors of $u$ must go to the neighbors of $f(u)$.
4. Last step: translate all the edges one by one and write that they are in $E_2$. If you like, with matrices: when you list the vertices in the order of $f$, the two adjacency matrices must be the same.

The $G$ and $H$ example in the questions is solved with exactly this method.

TIP · the complement trick. If comparing two graphs with many edges is hard, look at their complements. $G_1 \cong G_2 \iff \overline{G_1}\cong\overline{G_2}$, and the complements are sparser.

Common mistakes