Problem 1: Let κ(G) be the connectivity of G, let λ(G) be the edge connectivity of G, and let δ(G) be the minimum degree of G. Prove that κ(G) ≤ λ(G) ≤ δ(G) (assuming G has at least two vertices).
Problem 2: The d-dimensional cube is a graph with 2d vertices. Each vertex has a unique label of {0,1}d (each label is a unique sequence of d 0’s and 1’s), and two vertices are adjacent if and only if their labels differ in exactly one position. Determine the connectivity of the d-dimensional cube.
Problem 3: Find the smallest 3-regular (simple) graph with connectivity 1, and prove your answer.
Problem 4: Let G be a connected graph in which for every edge e there are cycles C1 and C2 both containing e and for which e is their only common edge. Prove that G is 3-edge-connected.
