[Solved] CSDS455 Homework8

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 2^d vertices. Each vertex has a unique label of {0,1}^d (each label is a unique sequence of d 0s and 1s), 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 C₁ and C₂ both containing e and for which e is their only common edge. Prove that G is 3-edge-connected.