Find an example of a chordal graph for which no minimum-degree vertex has a clique as its neighbors. (For this graph, it is not possible for a degeneracy ordering to be an elimination ordering.)
The slide "Example: Not all BFS orderings are lexicographic" from lecture 7a shows an example of a five-vertex graph, with lexBFS order a, b, d, e, c. To get an elimination order, we should reverse this, to give the elimination order c, e, d, b, a. But what if we forget to reverse it? Is the lexBFS order a, b, d, e, c an elimination order for this graph? Explain why or why not.
The slide "The pathwidth of trees" from lecture 7b shows three trees with pathwidth 1, 2, and 3. Label the vertices of the middle tree (the one with width 2) and find a path decomposition of width 2 of this tree. (Remember that this means a sequence of bags, with at most three vertices per bag, with each vertex appearing in a consecutive subsequence of the bags, and with each tree edge having both endpoints in at least one bag. Hint: explore the tree in depth-first order, with a bag for each edge, and then add extra vertices to some bags to ensure that every vertex appears consecutively.)
Recall that an independent set is a set of vertices that have no edges between any pair. The maximum independent set problem is the sort of maximum-weight optimization problem that can be solved using Courcelle's theorem, as long as we can describe the problem using a logical formula. Write a logical formula for the property that \(I\) is an independent set.
Your formula should leave \(I\) unquantified, but use for-all or exists quantifiers for all its other variables. As in the slides, use expressions like \(v\in I\) to test whether a vertex \(v\) belongs to set \(I\), and expressions like \(v.e\) to test whether vertex \(v\) is an endpoint of edge \(e\). The "vee" symbol \(\vee\) indicates the logical or of two subexpressions, and the "wedge" symbol \(\wedge\) indicates the logical and. You can use the symbol \(\lnot\) for logical negation. It may be easier to write a formula for the property that \(I\) is not an independent set, and then negate the whole formula.