Graphs: Basic Definitions & Properties
Graphs: Basic Definitions & Properties
A graph $G=(V,E)$ consists of vertices $V$ and edges $E\subseteq\binom{V}{2}$. Graph theory is the mathematics of networks: social connections, transportation systems, molecular bonds, and circuit diagrams all have natural graph representations. The key invariants — degree sequence, connectivity, and chromatic number — determine structural properties of the network.
Graph Fundamentals
A simple graph $G=(V,E)$ has $n=|V|$ vertices, $m=|E|$ edges, and degree sequence $(d_1,\ldots,d_n)$ where $d_i=|\{e\in E:v_i\in e\}|$. Handshaking lemma: $\sum d_i=2m$ (each edge contributes 2 to total degree). A graph is $k$-regular if all degrees equal $k$. Complete graph $K_n$: all $\binom{n}{2}$ edges; bipartite $K_{m,n}$: vertices split into parts of size $m,n$, every cross-edge present. A path $P_n$ and cycle $C_n$ are fundamental structures.
Euler Paths & Hamilton Cycles
An Euler path traverses every edge exactly once; an Euler circuit is a closed Euler path. Euler (1736): a connected graph has an Euler circuit iff every vertex has even degree; an Euler path iff exactly two vertices have odd degree. A Hamiltonian cycle visits every vertex exactly once; no simple characterization exists (NP-complete). Dirac's theorem: if $G$ has $n\geq 3$ vertices and every $d_i\geq n/2$, then $G$ has a Hamiltonian cycle.
Example 1
Does $K_5$ have an Euler circuit? An Euler path?
Solution: $K_5$: every vertex has degree $4$ (even). By Euler's theorem, $K_5$ has an Euler circuit. ✓. For an Euler path (open): we need exactly 2 odd-degree vertices, but $K_5$ has 0 odd-degree vertices — so any Euler path must close (is a circuit). Every Euler path in $K_5$ is actually a circuit.
Example 2
Is the Petersen graph Hamiltonian? (10 vertices, 3-regular)
Solution: The Petersen graph has no Hamiltonian cycle (can be shown by case analysis or using its girth-3 property). However, it does have Hamiltonian paths. Dirac's condition fails: $d_i=3<5=n/2$. The Petersen graph is the canonical example of a non-Hamiltonian 3-regular graph and appears as a minor in many non-Hamiltonian graphs.
Practice
- Prove the handshaking lemma and use it to show the number of odd-degree vertices is always even.
- Find a graph that is Eulerian (has an Euler circuit) but not Hamiltonian.
- Prove: if $G$ is connected and every vertex has even degree, then every edge lies in a cycle.
- Show $K_{3,3}$ is Eulerian and determine whether it has a Hamiltonian cycle.
Show Answer Key
1. Each edge contributes exactly 2 to $\sum\deg(v)$, so $\sum\deg(v)=2|E|$ (even). If the number of odd-degree vertices were odd, the sum would be odd — contradiction.
2. Example: $K_3\cup K_3$ (two disjoint triangles) — each component is Eulerian (all degrees even, connected), but not Hamiltonian (no single cycle visits all vertices since the graph is disconnected). For a connected example: take $K_4$ with one edge subdivided.
3. If $G$ is connected with all degrees even and edge $e=\{u,v\}$: removing $e$ makes $u,v$ odd-degree. If $G-e$ is connected, a path from $u$ to $v$ in $G-e$ plus $e$ forms a cycle. If $G-e$ is disconnected, $u$ and $v$ are in different components, contradicting the existence of the Euler circuit through $e$. (The edge lies in a cycle by Euler's theorem.)
4. $K_{3,3}$: all vertices have degree 3 (odd check fails for Eulerian — wait, degree 3 is odd). Actually $K_{3,3}$ has all vertices of degree 3, so $\sum\deg=18=2\cdot9$. Since degrees are odd, $K_{3,3}$ is NOT Eulerian. It does have a Hamiltonian cycle: $(1,4,2,5,3,6,1)$.