Скачать или смотреть Matching Theory Lecture-13 Part-I: Applications of ELP Theorem (to bicritical graphs & cubic graphs)

In today's lecture, we discussed a couple of applications of the ELP Theorem.

Firstly, we recalled that a MCG is bipartite if and only if it has zero bricks, and then we asked the analogous question: what are those MCGs that have zero braces? We used the ELP Theorem to answer this as follows:

A matching covered graph is bicritical if and only if has zero braces (that is, any application of the tight cut decomposition procedure to it yields only bricks).

Secondly, we proved that in a 2-connected cubic graph, every tight cut is a 3-cut; consequently, every tight cut is a barrier 3-cut.

For the above statement, we discussed an easy inductive proof using the Laminar ELP Theorem; however, we haven't proved the Laminar ELP Theorem thus far. Consequently, we also proved the above statement (inductively) using the weaker version (that is, the ELP Theorem) and the Uncrossing Lemma.

We say that a 2-connected cubic graph is essentially 4-edge-connected if its only 3-cuts are the trivial ones. It follows from the above that every essentially 4-edge-connected cubic graph is either a brick or a brace.

It is worth noting that a cubic brick need NOT be essentially 4-edge-connected; for example, the triangular prism. However, we observed that a connected bipartite cubic graph is a brace if and only if it is essentially 4-edge-connected.

In the second part, we discuss characterizations of braces, and we leave them as easy exercises for the audience members.