CS 263, Spring 2014, Homework 10

Due by email, 12:30pm, Thursday, June 12

1. What is the treewidth of the graph of a cube? Give an optimal tree-decomposition for this graph.

2. For each of the following graph properties, state whether the property can be expressed in FO, MSO₁ but not FO, MSO₂ but not MSO₁, or none of the above, and (when possible) provide or describe a formula in that logic for the property.

   1. Cubic graphs: graphs for which every vertex has exactly three incident edges.

   2. Chordal graphs: graphs for which every cycle of four or more edges has a diagonal edge.

   3. Graphs with an ABZ-coloring.

3. Define a graph to be even if it has an even number of edges, and odd otherwise.

   1. Suppose that $n\equiv 2\pmod{4}$ and that we choose a graph uniformly at random from the graphs with $n$ labeled vertices. What is the probability that the chosen graph is even?

   2. Use your answer to part (a) to prove that the property of being even does not have an FO formula.