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

For each of the following graph properties, state whether the property can be expressed in FO, MSO

_{1}but not FO, MSO_{2}but not MSO_{1}, or none of the above, and (when possible) provide or describe a formula in that logic for the property.Cubic graphs: graphs for which every vertex has exactly three incident edges.

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

Graphs with an ABZ-coloring.

Define a graph to be

*even*if it has an even number of edges, and*odd*otherwise.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?

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