Fulkerson, Delbert R.


The Berge-Fulkerson conjecture ★★★★

Author(s): Berge; Fulkerson

\begin{conjecture} If $G$ is a \Def[bridgeless]{bridge (graph theory)} \Def[cubic]{cubic graph} graph, then there exist 6 \Def[perfect matchings]{matching} $M_1,\ldots,M_6$ of $G$ with the property that every edge of $G$ is contained in exactly two of $M_1,\ldots,M_6$.

\end{conjecture}

Keywords: cubic; perfect matching

Syndicate content