Task list filter?

Choose required ranks and required tasks. The table of contents will list only tasks having one of the required ranks in corresponding rankings and at least one of the required tags (overall). If you wish to filter only according to some rankings or tags, leave the other groups empty.

Task rankings

Difficulty level

Task tags

Task type
«
«
«

Edge omission in cubic graph

Task number: 4047

Let G be a cubic graph without bridges. Prove it for each its edge there is a perfect matching that avoids it.

  • Hint

    Remove the edge from the graph and check Tutte’s condition, e.g. by a contradiction.

    Note that at least 3 edges lead from the odd components.

  • Solution

    Let G be a cubic graph without bridges. Cubic graphs satisfy Tutte’s condition, that is, for every SV(G) holds that |S|Co(G,S), where Co(G,S) stands for the number of odd components of the graph GS.

    When we remove the edge e, we assume for a contradiction that Ge does not have a perfect matching and therefore Tutte’s condition does not apply to it and there is a set SV(G) such that |S|<Co(Ge,S)

    If e had both ends in S or both ends in the same component, then Co(G,S)=Co(Ge,S) and we get the contradiction immediately. So necessarily e connects two odd components of Ge. They become one even by returning e in G. Thus Co(Ge,S)=Co(G,S)+2.

    These two components are not only connected to each other by the egde e, but are also connected to the set S. Because in the graph Ge these are odd components, an odd number of edges should lead into them according to the parity principle. Since the G graph has no bridges, there are at least three edges connecting each odd component (in both G and Ge). Similarly, at least two edges lead to even components. Thus, at least four edges connect the merged component in G. In total of at least 3Co(G,S)+4 edges lead to S.

    Conversely, in Ge, it holds that |S|<Co(Ge,S). Both sides are integers, so 3|S|<3Co(Ge,S)2.

    Because G is cubic, vertices of S are incident with at most 3|S| edges. Therefore, for the number of edges #e incident with S in the graph G the following inequality holds: 3Co(G,S)+4#e3|S|<3Co(Ge,S)2=3(Co(G,S)+2)2=3Co(G,S)+4, which is the desired contradiction.

Difficulty level: Hard task
Proving or derivation task
Complex task
Cs translation
Send comment on task by email