Graphs with unique 1-Factorization Let $G(V,E)$ be a graph with a 1-factorizations $M$ and $m=|M|$ 1-factors. I am searching for graphs with unique 1-factorizations (i.e. there is only one 1-factorization).
Examples:


*

*Cyclic graph $C_n$ with even $n$, with $m=2$ 1-factors.

*Complete graph $K_4$, with $m=3$ 1-factors.


(Some graphs have unique 1-factorizations under isomorphism, such as the 3-prism graph $Y_3$, but I am not interested in those.)


*

*Are there other examples?

*What is the maximum number $m$ of 1-factors, when $G$ has a unique 1-factorization?


I conjecture that the answer to question 2 is $m=3$ (for $K_4$), but I don't know how to prove that.
I would be very happy for every hint to an answer or a relevant literature.
 A: If there is only one edge colouring with $k$ colours of a graph with chromatic index $k$, the graph is said to be "uniquely edge colourable".  If you search on that phrase (with and without the second "u") you will find that the problem is trivial for $k\le 2$, solved for $k\ge 4$ (only case $K_{1,k}$) and for $k=3$ can be reduced to the case of cubic graphs. For example, see this paper of Andrew Thomason. It is said that an example is the generalized Petersen graph $P(9,2)$.
A: This is just to expand a little bit on Brendan's answer.
For cubic graphs, there is a construction that gives a large number of uniquely 3-edge colourable graphs: start with $K_4$, and repeatedly insert a vertex of degree 3 into a triangular face. This gives a bunch of uniquely-4-colourable planar triangulations (in fact, it is known that this family contains all the uniquely-4-colourable planar triangulations) so the duals of these graphs form a large class of uniquely 3-edge colourable cubic graphs.
Of course, all of these graphs are planar and so at one stage, some optimist conjectured that this was the entire collection of uniquely 3-edge colourable cubic graphs. The $P(9,2)$ example referred to in Brendan's answer is the smallest non-planar cubic graph that is uniquely 3-edge colourable, though lots more such graphs are known.
Related to all this is the question of when a cubic graph has exactly 3 Hamilton cycles. Certainly any uniquely 3-edge colourable cubic graph has exactly 3 Hamilton cycles, but the converse is not true. Thomason found a family of cubic graphs (more generalised Petersen graphs) with exactly 3 Hamilton cycles that are not uniquely 3-edge colourable. The smallest of Thomason's examples is $P(15,2)$ and I wonder if this is actually the smallest possible example. Before you ask, Brendan, I have checked up to 26 vertices, so there might be some examples hiding on 28 vertices but no smaller.
