Editing Uniquely colorable graph (section)

===Unique edge colorability===
[[File:Generalized Petersen 9 2 edge coloring.svg|thumb|The unique 3-edge-coloring of the [[generalized Petersen graph]] ''G''(9,2)]]
A '''uniquely edge-colorable graph''' is a [[Edge coloring|''k''-edge-chromatic]] graph that has only one possible [[Edge coloring|(proper) ''k''-edge-coloring]] up to permutation of the colors. The only uniquely 2-edge-colorable graphs are the paths and the cycles. For any ''k'', the [[Star (graph theory)|stars]] ''K''<sub>1,''k''</sub> are uniquely ''k''-edge-colorable.  Moreover, {{harvtxt|Wilson|1976}} conjectured and {{harvtxt|Thomason|1978}} proved that, when ''k'' ≥ 4, they are also the only members in this family. However, there exist uniquely 3-edge-colorable graphs that do not fit into this classification, such as the graph of the [[triangular pyramid]].

If a [[cubic graph]] is uniquely 3-edge-colorable, it must have exactly three [[Hamiltonian cycle]]s, formed by the edges with two of its three colors, but some cubic graphs with only three Hamiltonian cycles are not uniquely 3-edge-colorable.{{sfnp|Thomason|1982}}
Every simple [[planar graph|planar]] cubic graph that is uniquely 3-edge-colorable contains a triangle,{{sfnp|Fowler|1998}} but {{harvs|first=W. T.|last=Tutte|year=1976|authorlink=W. T. Tutte|txt}} observed that  the [[generalized Petersen graph]] ''G''(9,2) is [[planar graph|non-planar]], triangle-free, and uniquely 3-edge-colorable. For many years it was the only known such graph, and it had been conjectured to be the only such graph<ref>{{harvtxt|Bollobás|1978}}; {{harvtxt|Schwenk|1989}}.</ref> but now infinitely many triangle-free non-planar cubic uniquely 3-edge-colorable graphs are known.{{sfnp|belcastro|Haas|2015}}