3 Width The width of a graph G is the smallest number w such that there is a permutation of G's vertices so that every vertex in the sequence is connected to at most w vertices that precede it in the sequence. a) Prove that any graph with maximum degree w has width w. b) Prove that every graph with width w is (w+ 1)-colorable. c) Give an example of a 2-colorable graph with width at least n. 3 Width The width of a graph G is the smallest number w such that there is a permutation of G's vertices so that every vertex in the sequence is connected to at most w vertices that precede it in the sequence. a) Prove that any graph with maximum degree w has width w. b) Prove that every graph with width w is (w+ 1)-colorable. c) Give an example of a 2-colorable graph with width at least n