Definition 4.1. For a positive integer k, a graph G is k-connected if, for every m < k, and every v1, . . . vm ∈ V (G), deleting v1, . . . vm results in a connected graph or a single vertex. Definition 4.2. The connectivity of a graph G, κ(G), is the largest k such that G is k-connected. Example 4.3. The following were explained in lecture, and we leave as an exercise in these notes: • Trees are 1-connected but not 2-connected, so if T is a tree, κ(T ) = 1; • Cycles are 2-connected, but not 3-connected, so if C is a cycle, κ(C) = 2. • For the complete graph Kn, κ(Kn) = n − 1; • For any graph G, regardless of κ(G), Adding a single vertex to G, and connecting it by one edge to the rest of G reduces the connectivity to 1. We sometimes want to zoom in on a particular part of a graph and measure how well connected two particular vertices are. Definition 4.4. For non-adjacent vertices a, b ∈ V (G), an a, b-separator is a subset S of V (G) such that there is no path from a to b in G − S. Exercise 4.5. • If there is a pair of vertices a, b ∈ G and a separator S of size k, then κ(G) ≤ k. • κ(G) is the minimal size of an a, b-separator, taken over pairs a, b of non- adjacent vertices.

answer the exercise