Two unmatchable edges

Task number: 4045

Construct a cubic graph without bridges that contains two non-adjacent edges that do not together belong to any common matching.

  • Hint

    Explore matching of a small complete graph and also possible operations with this graph.

  • Solution

    The complete graph \(K_4\) has a unique partition into perfect matchings. Take two copes of \(K_4\), in each choose an edge, delete these two and then add edges between vertices of degree two to make this graph connected.

    The newly added edges can be extended to a unique matching, so it is easy to pick one of them and a non-matchable edge from the rest, see the picture.

    a graph
Difficulty level: Easy task (using definitions and simple reasoning)
Reasoning task
Cs translation
Send comment on task by email