Investigating Solitude in 2-Connected 3-Regular Graphs and in r-Graphs Through the Lens of CLM’s Dependence Relation

The study of perfect matchings (aka 1-factors) in 2-connected 3-regular graphs goes back to the Four Color Problem. Schönberger (1934) proved that, in any such graph, each edge belongs to at least one perfect matching; this fact is easily deduced using Tutte’s 1-factor Theorem (1947). We say that an edge is solitary if it belongs to precisely one perfect matching. Schönberger’s result naturally leads to the following problems in the context of 2-connected 3-regular graphs: (i) characterise solitary edges, and (ii) prove bounds on the number of solitary edges.

In a recent work, Goedgebeur, Mattiolo, Mazzuoccolo, Renders, and Wolf proved that, in any 3-connected 3-regular graph, there are at most six solitary edges, and they also provided a complete characterisation of those that have three or more solitary edges.

In a joint work with Narayana, Mattiolo, and Gohokar, we generalise their results—characterisations as well as bounds—to 3-edge-connected r-graphs. An r-graph is any r-regular graph with the additional property that each odd cut has at least r edges; when r = 3, this is precisely the class of 2-connected 3-regular graphs. Using Tutte’s 1-factor Theorem, one may easily generalise the aforementioned result of Schönberger to all r-graphs.

We make extensive use of the dependence relation introduced by CLM (Carvalho, Lucchesi, and Murty) in 1999, and this is precisely what allows us to obtain stronger results. In this talk, I shall discuss all of this, including the historical context alluded to earlier. Basic familiarity with graph theory is expected; nothing beyond that.