Key Takeaways: Introduction to Graphs

A one-page reference card. Reread it before an exam or before modeling your next network.

Core definition

A graph $G=(V,E)$: a finite non-empty vertex set $V$ and an edge set $E$. In a simple graph (the default) each edge is an unordered pair $\{u,v\}$ of distinct vertices — no loops, no parallel edges. A multigraph allows loops and/or parallel edges.

  • Max edges in a simple graph on $n$ vertices: $\displaystyle\binom{n}{2}=\frac{n(n-1)}{2}$.
  • An edge is a 2-element subset of $V$ (Ch. 8); counting them is $\binom{n}{2}$ (Ch. 16).

Local terminology

Term Symbol Meaning
Adjacent — $\{u,v\}\in E$
Incident — edge $e$ touches its two endpoints
Neighborhood $N(v)$ $\{u \mid \{u,v\}\in E\}$
Degree $\deg(v)$ edges at $v$; $=\lvert N(v)\rvert$ in a simple graph
Isolated — $\deg(v)=0$
Leaf / pendant — $\deg(v)=1$

Global terminology (getting around)

Term Repeats allowed? Closed? Min length
Walk vertices may repeat either 0
Path no repeated vertex open 0
Cycle no repeats except endpoints closed 3 (simple graph)
  • Length = number of edges.
  • Connected: a path joins every pair of vertices. Otherwise the graph splits into connected components (maximal connected pieces).
  • "Reachable by a path" is an equivalence relation (Ch. 12); its classes = the components.

Trap: "path" is overloaded. Here a path has no repeated vertex; a route that may repeat is a walk. Always check the local definition.

Graph types — each adds ONE feature

Type Added feature Degree notion Models
Undirected (default) edges unordered $\{u,v\}$ $\deg(v)$ friendship
Directed (digraph) edges ordered $(u,v)$ in $\deg^-(v)$, out $\deg^+(v)$ follows, links, deps
Weighted $w\colon E\to\mathbb{R}$ — distance, cost, capacity
Bipartite $V=X\cup Y$, edges cross only — applicants–jobs
Complete $K_n$ every pair joined all $=n-1$ dense / worst case
  • $K_n$: $\binom{n}{2}$ edges, every degree $n-1$. Complete bipartite $K_{m,n}$: $mn$ edges.
  • Bipartite $\iff$ no odd cycle. (2-coloring revisited in Ch. 33.)
  • A digraph is a relation (Ch. 12) drawn; symmetric relation $\equiv$ undirected graph.

Handshaking lemma (memorize)

$$\sum_{v\in V}\deg(v) = 2\lvert E\rvert.$$

  • Proof in one line: double-count (vertex, edge) incidences — by vertex $\Rightarrow \sum\deg(v)$; by edge $\Rightarrow 2\lvert E\rvert$. Same set, so equal.
  • $\Rightarrow$ the sum of all degrees is even, and $\lvert E\rvert=\frac{1}{2}\sum\deg(v)$.

Corollary (lie detector): the number of odd-degree vertices is even.

Claim Verdict
7 people each shook exactly 3 hands Impossible — 7 odd-degree vertices (odd count); $7\cdot 3=21$ odd
6 people each shook exactly 3 hands Possible — $\sum\deg=18$, so $\lvert E\rvert=9$
Degree sequence $(4,3,3,2,2)$ Possible — two odd degrees (even count); $\lvert E\rvert=7$

Isomorphism $G_1\cong G_2$

A bijection $f\colon V_1\to V_2$ with $\{u,v\}\in E_1 \iff \{f(u),f(v)\}\in E_2$ (adjacency preserved and reflected). "Same graph, different name tags."

Decision rule:

To REFUTE isomorphism  -> find a differing INVARIANT (start: sorted degree sequence).
To PROVE  isomorphism  -> exhibit the bijection and check every pair.
Degree sequences match -> NECESSARY but NOT SUFFICIENT (keep checking).
Degree sequences differ -> NOT isomorphic (done).
Invariant (preserved by every isomorphism)
$\lvert V\rvert$, $\lvert E\rvert$
sorted degree sequence
number of connected components
number of cycles of each length (e.g. triangles)
  • Brute force = $n!$ relabelings (e.g. $15!\approx 1.3\times10^{12}$) — impractical; use invariants.

Modeling checklist (ask in this order)

1. What is a VERTEX?      (person, intersection, page, module, course)
2. What is an EDGE?       (friendship, road, link, dependency, prerequisite)
3. DIRECTED or UNDIRECTED?  mutual -> undirected;  one-way -> directed
4. WEIGHTED or not?         carries cost/distance/capacity -> weighted
Domain Vertex Edge Directed? Weighted?
Friendship person "is friends with" undirected usually no
Following person "follows" directed no
Road map intersection road segment mixed yes (distance/time)
Web page hyperlink directed optional
Software build module "depends on" directed no (cycle = bug)

Common pitfalls

  • Confusing walk (repeats ok) with path (no repeats).
  • Confusing connected (one piece) with complete (all pairs joined).
  • Treating a directed edge as a set — it is an ordered pair $(u,v)\ne(v,u)$.
  • Claiming isomorphism from matching degree sequences (necessary, not sufficient).
  • A graph with exactly one odd-degree vertex (impossible — violates the corollary).
  • Allowing a self-loop $\{v,v\}$ in a simple graph (it is a multigraph feature).

Toolkit additions (graphs.py, begun)

Member Returns
Graph() empty undirected simple graph (adjacency dict)
add_vertex(v) inserts v (no-op if present)
add_edge(u, v) adds undirected edge; raises on self-loop
neighbors(v) the set $N(v)$
degree(v) $\deg(v)=\lvert N(v)\rvert$
vertices() the vertex set $V$
degree_sum() $\sum_v\deg(v)$
num_edges() $\lvert E\rvert=$ degree_sum() // 2 (handshaking lemma)

(Ch. 28 adds bfs, dfs; Ch. 29 dijkstra; Ch. 32 mst_kruskal; Ch. 34 max_flow.)