Given a bridgeless cubic graph G , the four perfect matching defect of G , denoted by d PM (G) , is the minimum number of edges of G left uncovered over all sets of four perfect matchings. The defect of a matching is the number of vertices it leaves uncovered divided by two. The four matching cover defect of G , denoted by d M (G) , is the minimal sum of defects of matchings over all matching covers of G containing four matchings. We show that G always has a matching cover containing two perfect and two non-perfect matchings and that G has a matching cover containing three perfect matchings and one non-perfect matching if and only if the Fan-Raspaud conjecture holds for G. We establish that d M (G) ≤ d PM (G). We show that for each integer k , there exists a nontrivial snark G with d M (G) = d PM (G) = k; that is, there are nontrivial snarks that are far from being coverable by four perfect matchings. Finally, we present another family of nontrivial snarks, where for each integer k there exists a nontrivial snark G with 2 d M (G) ≤ d PM (G) = 2 k .

A cycle cover of a graph is a collection of cycles such that each edge of the graph is contained in at least one of the cycles. The length of a cycle cover is the sum of all cycle lengths in the cover. We prove that every bridgeless cubic graph with $m$ edges has a cycle cover of length at most $212/135 \cdot m \ (\approx 1.570 m)$. Moreover, if the graph is cyclically $4$-edge-connected we obtain a cover of length at most $47/30 \cdot m \approx 1.567 m$.

We prove that every simple bridgeless cubic graph with $n \ge 8$ vertices has a traveling salesman tour of length at most $1.3\cdot n - 2$, which can be constructed in polynomial time.

We show that every bridgeless cubic graph $G$ with $m$ edges has a cycle cover of length at most 1.6 m. Moreover, if $G$ does not contain any intersecting circuits of length 5, then $G$ has a cycle cover of length $212/135 \cdot m \approx 1.570 m$, and if $G$ contains no 5-circuits, then it has a cycle cover of length at most $14/9 \cdot m \approx 1.556 m$. To prove our results, we show that each 2-edge-connected cubic graph $G$ on $n$ vertices has a 2-factor containing at most $n/10+f(G)$ circuits of length 5, where the value of $f(G)$ depends only on the presence of several subgraphs arising from the Petersen graph. As a corollary we get that each 3-edge-connected cubic graph on $n$ vertices has a 2-factor containing at most n/9 circuits of length 5, and each 4-edge-connected cubic graph on $n$ vertices has a 2-factor containing at most n/10 circuits of length 5.

We show that every 2-edge-connected cubic graph $G$ not isomorphic to the Petersen graph has a 2-factor with at most 2(n-2)/15 circuits of length 5, where $n$ is the number of vertices of $G$. We construct an infinite family of graphs, for which this bound is tight, and improve the bound to n/10 for cyclically 4-edge-connected cubic graphs of girth at least 5. We also show that $G$ has a $2$-factor with at most $n/5.8\overline{3}$ odd circuits.

For every rational number r such that $3