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.