Orientation is an assignment of direction to each edge of an undirected graph. When none of the directed edges is in a cycle, the orientation is called acyclic. When every directed edge is in some cycle, the orientation is called totally cyclic.

A spanning tree of an undirected graph is a connected subgraph, including all its vertices, but containing no cycles. The number of spanning trees seems to have a relationship with the numbers of acyclic and totally cyclic orientations of the graph. Yet, proof of such a relation for a general graph is still elusive.

The Merino-Welsh conjecture, the subject of this paper, suggests that the maximum of the numbers of acyclic and totally cyclic orientations will always be greater than or equal to the number of spanning trees of a bridgeless and loopless graph. It is an interesting problem to prove, and the authors have done an excellent job in establishing it for a special class of graphs.

Starting with an engaging introduction, where the background material is quickly presented along with examples, the authors lead us into lemmas in section 2, which explore the characteristics of a minimal counterexample to the conjecture. The discussion moves onto two terminal series parallel (TTSP) graphs in section 3. Duality that respects the terminals, called sp-duality, is introduced. Lemmas that track the relations between the parameters of interest through the series/parallel connection are rendered.

The core contributions of the paper are outlined in section 4. The multiplicative form of the Merino-Welsh conjecture is where the difficulty is, and the replaceability of a TTSP graph by another is defined in terms of this form. Further, a TTSP graph is called reducible if it can be replaced by another with fewer edges. Extendibility is defined based on the series/parallel class of each edge. By making use of lemmas on these concepts, a procedure to systematically construct all series-parallel graphs is provided and leads to the desired result. Surprisingly, all of the extendable and irreducible TTSP graphs can be shown in a short list, as demonstrated in a table in the paper.

Overall, this is an impressive paper with an absorbing substantiation of the combinatorics involved.