Study Notes – Combinatorics
Topic: Basic Definitions (Vertices, Edges, Paths, Cycles)
Audience: Undergraduate students (MIT‑level) preparing for the International Mathematical Olympiad (IMO).
Goal: Build a rigorous, first‑principles foundation that also hints at deeper theory and subtle edge cases.
All graphs are finite unless stated otherwise.
1. Graphs – The Formal Definition
A graph (G) is a pair (G=(V,E)) where
| Symbol | Meaning | Notes |
|---|---|---|
| (V) | Set of vertices (or nodes) | Often denoted (V(G)). |
| (E) | Set of edges | Each (e\in E) is a 2‑tuple of vertices. |
1.1 Types of Graphs
| Type | Definition | Edge representation |
|---|---|---|
| Undirected simple graph | No loops, no parallel edges. | Each (e={u,v}) with (u\neq v). |
| Undirected multigraph | Parallel edges allowed, but no loops. | (e=(u,v)) may appear multiple times. |
| Undirected graph with loops | Loop edges ((v,v)) allowed. | Often excluded in IMO problems. |
| Directed graph (digraph) | Each edge has a direction. | Edge represented as an ordered pair ((u,v)). |
| Weighted graph | Each edge (e) has a weight (w(e)\in\mathbb{R}). | Usually only defined for undirected graphs. |
| Bipartite graph | Vertex set partitions into (X,Y) s.t. all edges go from (X) to (Y). | No edges within (X) or within (Y). |
Notation
- (N(v)) denotes the set of neighbors of (v).
- (d(v)=|N(v)|) is the degree of (v).
- (E(G)) and (V(G)) are used for clarity when the graph is implicit.
2. Incidence, Adjacency, and Matrices
2.1 Incidence Matrix
Given (G=(V,E)) with (|V|=n), (|E|=m), the incidence matrix (I\in{0,1}^{n\times m}) is defined by
[ I_{v,e} = \begin{cases} 1, & \text{if } v \text{ is incident to } e,\ 0, & \text{otherwise}. \end{cases} ]
For directed graphs (I_{v,e}=1) if (v) is the tail of (e) and (-1) if it is the head.
2.2 Adjacency Matrix
Similarly, the adjacency matrix (A\in\mathbb{Z}^{n\times n}) is
[ A_{u,v} = \begin{cases} \text{number of edges between } u \text{ and } v, & \text{if } u\neq v,\ \text{number of loops at } u, & \text{if } u=v. \end{cases} ]
For simple undirected graphs, (A_{u,v}\in{0,1}) and (A) is symmetric.
Theorem (Degree–Matrix Relation).
For any graph (G) with adjacency matrix (A) and degree vector (\mathbf{d}), [ D = \operatorname{diag}(d(v_1),\dots,d(v_n)) = A\mathbf{1}, ] where (\mathbf{1}) is the all‑ones vector.
3. Paths and Cycles – Formal Definitions
3.1 Walks
A walk (W) of length (\ell) in (G) is an alternating sequence of vertices and edges
[ v_0,e_1,v_1,e_2,\dots,e_\ell,v_\ell ]
such that for each (i), the edge (e_i) connects vertices (v_{i-1}) and (v_i) (or directed as appropriate).
Walks may repeat vertices and edges.
3.2 Trails
A trail is a walk with no repeated edges.
Vertices may repeat.
3.3 Paths
A path is a walk (or trail) with no repeated vertices (hence automatically no repeated edges).
All paths are simple, but not all simple walks are paths.
3.4 Cycles
A cycle is a closed walk where
- The first and last vertex coincide: (v_0 = v_\ell).
- All other vertices are distinct (and hence all edges are distinct).
The length of a cycle is the number of edges (or vertices) in it.
A simple cycle is a cycle with no repeated vertices other than the first/last.
3.5 Edge‑disjoint and Vertex‑disjoint
- Edge‑disjoint: two subgraphs share no edges.
- Vertex‑disjoint: two subgraphs share no vertices.