Let $G\left(V,E\subset V\times V,\omega: V\supset \lbrace u,v\rbrace\mapsto w_{uv}\in\mathbb{R}\right);\ \left|e_{uv}\right|:=\omega_{uv}\quad$ be a cubic symmetric graph that contains a vertex-disjoint cycle cover.
Question:
- Suppose our task is to remove from $G$ all edges that do not belong to to the vertex-disjoint cycle cover of minimal weight.
- Suppose further that we have the aid of an oracle that always presents us the set of remaining edges, from which we can delete an arbitrary one without destroing all of the remaining cycle covers.
What is the better strategy of choosing the next edge to be deleted:
- delete the longest edge?
- scrutinize the $K_4$ that are induced by the neighborhood of vertices that are adjacent to a candidate edge and then delete longest edge that is one of the "diagonals" of an induce $K_4$?
The image depicts one of the claw graphs that are subgraphs of $G$; the edge that constitutes to the diagonals of the induced $K_4$ is highlighted in red.
By diagonals I mean the pair of edges of a $K_4$ that constitutes to its perfect matching of maximal weight.
In the depicted claw graph the diagonal-edge isn't the longest edge in the graph, which may make it seem ridiculous that its deletion may yield a shorter cycle cover than deleting the longest edge.
Note however that the set of edges that constitutes to the lightest cycle cover is invariant under the addition of vertex-weights, aka vertex potentials, and so is the relative order of the perfect matchings in a weighted $K_4$, whereas the relative order of the edge's lengths may change arbitrarily.
