CS 263, Spring 2014, Homework 9

Due at the start of class, Thursday, June 5

1. A multigraph is a graph in which there may be more than one edge between the same pair of vertices.

   1. Show that the subgraph relationship between $k$-vertex multigraphs is a well-quasi-order

   2. For graphs that are not multigraphs, the induced subgraph relationship among graphs that have vertex cover $k$ is a well-quasi-order. Show that this is not true for multigraphs.

2. Show that the complete bipartite graph $K_{2,4}$ is a minor of the graph of a cube.

3. Prove that the length of the longest simple cycle in a given graph is a minor-monotone property of graphs.