CSDS 455: Applied Graph Theory
Homework 8
Next week, we will be studying k-connected graphs. You should look through the section of your text on
k-connectivity and/or cuts. You should be familiar with the terms connectivity, edge connectivity, cut vertex,
bridge, and block.
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.
