Graph Fundamentals and Types

A graph is a set of vertices (nodes) $V$ together with a set of edges $E$ joining pairs of them. Almost any relation can be modelled as one — the skill is noticing when a problem is a graph problem.

• Order: $n=|V|$ · Size: $m=|E|$
• Degree $\mathrm{deg}(v)$ — number of incident edges; split into in-degree and out-degree when directed.

Edges may be undirected or directed, weighted or unweighted.

---

Taxonomy

Category	Type	Definition
Direction	Undirected	$(u,v)$ implies $(v,u)$
	Directed (digraph)	every edge is one-way
Weights	Unweighted	every edge costs 1
	Weighted	each edge carries a cost, length or capacity
Edge rules	Simple	no self-loops, no parallel edges
	Multigraph	parallel edges allowed
	Pseudograph	self-loops and parallel edges allowed
Connectivity	Connected	every pair has a path between them
	Disconnected	some pair has none
	Component	a maximal connected subgraph
Structure	Complete	every pair joined by exactly one edge
	Regular	every vertex has the same degree
	Bipartite	vertices split into two sets, every edge crosses
Cycles	Cyclic / Acyclic	contains a cycle, or does not
	Tree	connected, undirected, acyclic
	Forest	acyclic, possibly disconnected
Rooting	Out-tree (arborescence)	rooted, all edges point away from the root
	In-tree (anti-arborescence)	rooted, all edges point toward the root

Special named graphs

1. DAG — directed, no directed cycle. A topological ordering exists. Every finite DAG has at least one source and one sink.
2. Complete bipartite $K_{m,n}$ — every vertex of one side joined to every vertex of the other; $mn$ edges.
3. Path graph $P_n$ — a single simple path; two vertices of degree 1, the rest degree 2.
4. Star $K_{1,n-1}$ — one centre of degree $n-1$, all others leaves.
5. Wheel $W_n$ — a cycle plus a centre adjacent to every cycle vertex.
6. Hypercube $Q_d$ — vertices are $d$-bit strings, adjacent when they differ in one bit. $2^d$ vertices, $d{2}^{d-1}$ edges, $d$-regular.
7. Tournament — an orientation of a complete graph; exactly one directed edge per pair. A transitive tournament is a DAG.
8. Complement $\overline{G}$ — same vertices, adjacency inverted.
9. Line graph — one vertex per edge of $G$; adjacent when the edges share an endpoint.
10. Caterpillar — a tree that becomes a path once all leaves are removed.
11. Chordal — every cycle of length $\ge 4$ has a chord. Includes trees and complete graphs.
12. Planar — drawable with no crossings; $V-E+F=2$ and $E\le 3V-6$.
13. Eulerian — has a closed walk using every edge once; connected with all degrees even. See Eulerian Paths.
14. Semi-Eulerian — has an Eulerian path; exactly two odd-degree vertices.
15. Hamiltonian — has a cycle visiting every vertex once. No usable characterisation is known — deciding it is NP-complete.
16. Semi-Hamiltonian — has a Hamiltonian path but perhaps no cycle.

---

Terminology

Term	Meaning
Adjacent vertices	joined by an edge
Incident edge	an edge touching a given vertex
Path	a sequence of vertices with consecutive ones adjacent
Path length	number of edges in the path
Simple path	no repeated vertex
Cycle	a path returning to its start with no repeated interior vertex
Leaf / pendant	degree 1
Isolated vertex	degree 0
Bridge (cut edge)	removing it increases the component count
Articulation point (cut vertex)	removing it increases the component count
Subgraph	a subset of vertices and edges
Spanning subgraph	contains all vertices
Spanning tree	a spanning subgraph that is a tree

---

Theorems worth memorising

Result	Statement
Handshake lemma	${\sum }_v\mathrm{deg}(v)=2m$ — the degree sum is always even, so the number of odd-degree vertices is even
Bipartite characterisation	$G$ is bipartite iff it has no odd cycle
Tree characterisation	connected and exactly $n-1$ edges (any two of: connected, acyclic, $n-1$ edges, implies the third)
Forest edge count	a forest with $c$ components has $n-c$ edges
Complete graph edges	$\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}$
Max edges, simple undirected	$\frac{n(n-1)}{2}$
Max edges, simple directed	$n(n-1)$
Planar edge bound	$E\le 3V-6$ for $V\ge 3$; $E\le 2V-4$ if triangle-free
Euler’s formula	$V-E+F=2$ for a connected planar graph

See also: Representations · Graph Theory