  The problem of establishing the number of perfect matchings necessary to
cover the edge-set of a cubic bridgeless graph is strictly related to a famous
conjecture of Berge and Fulkerson. In this paper we prove that deciding whether
this number is at most 4 for a given cubic bridgeless graph is NP-complete. We
also construct an infinite family $\cal F$ of snarks (cyclically
4-edge-connected cubic graphs of girth at least five and chromatic index four)
whose edge-set cannot be covered by 4 perfect matchings. Only two such graphs
were known. It turns out that the family $\cal F$ also has interesting
properties with respect to the shortest cycle cover problem. The shortest cycle
cover of any cubic bridgeless graph with $m$ edges has length at least
$\tfrac43m$, and we show that this inequality is strict for graphs of $\cal F$.
We also construct the first known snark with no cycle cover of length less than
$\tfrac43m+2$.

Combinatorics