• Overview
• Details
• Exercises

Graphs model relationships between entities. We cover undirected graphs, directed graphs (digraphs), multigraphs, degrees, paths/cycles, and connectivity basics used throughout algorithms and networks.

• Definitions: V (vertices), E (edges). Simple graph vs multigraph (parallel edges), loops; digraphs (ordered edges).
• Degree: deg(v) (undirected), in-degree/out-degree (directed). Handshaking lemma: Σ deg(v) = 2|E|.
• Representation: adjacency list vs matrix; trade-offs for |V|,|E|.
• Paths, cycles, simple paths; distance, diameter, eccentricity.
• Connectivity: connected components (undirected), strongly/weakly connected (directed).
• Special graphs: complete K_n, bipartite, trees, DAGs, planar graphs (previews).

1. Prove the handshaking lemma and its directed analogue (sum of in-degrees equals sum of out-degrees equals |E|).
2. Given an adjacency matrix, compute degrees and identify isolated vertices.
3. Decide whether a given digraph is strongly connected; if not, list SCCs.