Worksheet for Question 1: Pfaffian orientations.

Apply clockwise BFS to this graph with root vertex 0, first child 1, and direction clockwise to create a BFS tree.

(a) Label the remaining vertices with 2, 3, ... according to their Breadth-First indices.

(b) Colour the BFS tree arcs with a GREEN pen and direct these arcs so that the arc for each vertex u is directed from u to the parent of u in the BFS tree.

(c) Complete this to a Pfaffian orientation by colouring the remaining directed edges with a RED pen.

(d) Number the red edges 1, 2, 3, ... in the same order as you used when making your decisions about how to orient the edges.