Graph Theory – Perfect Matching Problem of Planar Graph

Question

We know that connectivity is closely related to the Hamiltonian of planar graphs.
The most famous result is the Tutte theorem.

Theorem (Tutte, 1956). A 4-connected planar graph has a Hamiltonian cycle.

It's worth noting that this theorem was later extended.
For example: Thomassen proves one of Plummer's conjectures: Every 4-connected planar graph is Hamiltonian-connected.

Anyway, Tutte's theorem follows that any 4-connected planar graph $G$ has an almost perfect matching, and in the case of even order, $G$ has a perfect matching.

I have a potentially naive question:

If we do not use Tutte's theorem, can we prove that any 4 connected planar
graph has an almost perfect matching? What are the possible directions of proof?

Because of Tutte's strong results, there seem to be fewer ways to determine if a planar graph contains a perfect matching (or people don't pay much attention to it).

I wonder if anyone has ever dealt with this problem.

Answer 1

The following article provides a positive answer to my question. Yes, it is possible to prove that a 4-connected planar graph has a perfect matching or almost perfect matching even without using the Hamiltonian property.

• Biedl, Therese, et al. "Tight bounds on maximal and maximum matchings." Discrete Mathematics 285.1-3 (2004): 7-15.

Here is my selective excerpt (because the authors also did something else in the same article).

1. First, the authors introduce the concept of the 4-block tree.

Similar to the 2-block tree, we can define a 4-block tree that captures the relationships among the 4-connected components of a graph (Fig. 2). Recall that a graph is 4-connected if removing any three arbitrary vertices leaves a connected graph. Assume that a graph is 3-connected, but not 4-connected. Then it contains three vertices $\{v, w, x\}$ such that removing them from the graph yields at least two connected components; we call $\{v, w, x\}$ a separating triplet. For each connected component $C$ obtained from removing $\{v, w, x\}$, we create a new graph by adding to $C$ the vertices $v, w, x$, as well as all their edges incident to another vertex in $C$, and the three edges $(v, w),(w, x)$ and $(x, v)$ if they did not exist already.

We iterate this process until all resulting graphs are 4-connected; these are the 4-connected components of the graph. The 4-block tree is then defined as follows. We create one node for every 4-connected component, and one node for every separating triplet, and add an edge if and only if the separating triplet was contained in the 4-connected component. The resulting graph is again a tree. We denote its number of leaves by $\ell_4(G)$, or just $\ell_4$ if the graph is clear from the context.

Note that each leaf of the 4-block tree corresponds to some subgraph of $G$ that would be 4-connected if we added all edges between the vertices of the separating triplet that defined it.

2. Main theorem.

Nishizeki and Baybars showed that every 3-connected planar graph has a matching of size $\frac{n+4}{3}$ [9]. In this section, we strengthen this result by including the number of leaves of the 4-block tree in the bound; in particular we obtain a bound that resolves to $\left\lfloor\frac{n}{2}\right\rfloor$ if the graph is 4-connected.

Theorem 3. Any 3-connected planar graph $G$ of order $n$ has a matching of size $\min \left\{\frac{n-1}{2}, \frac{2 n+4-\ell_4}{4}\right\}$, where $\ell_4$ is the number of leaves of the 4-block tree of $G$.

Proof. Let $G$ be a 3-connected planar graph of order $n$, and let $M$ be a maximum matching in $G$. By Theorem 2 , there exists a vertex set $T$ in $G$ such that there are exactly $\left|V_{\neg M}\right|=\operatorname{odd}(T)-|T|$ unmatched vertices in $M$. If $|T| \leqslant 2$, then $G-T$ is still connected, i.e., $\left|V_{\neg M}\right| \leqslant \operatorname{odd}(T) \leqslant 1$. But then clearly $|M| \geqslant \frac{n-1}{2}$.

If $|T|=3$, then there can be at most two odd components in $G-T$. If there were three or more components, they would all have to be incident to all vertices of $T$ by 3 -connectivity, and the graph would contain $K_{3,3}$ as a minor. But $G$ is planar, so this is impossible. Since we assumed that there are $\operatorname{odd}(T)-|T|<0$ unmatched vertices, this case is actually impossible.

If $|T| \geqslant 4$, then we greedily add edges between any two non-adjacent vertices of $T$ that lie on the same face of $G$, without destroying the planarity of the graph. Let $G_T$ denote the subgraph of this augmented graph induced by the vertices of $T$ (see Fig. 3). Note that no two components of $G-T$ can be within the same face of $G_T$, because then we would have introduced an edge to split the face between them. Therefore, for every odd component there must be a unique face in $G_T$. This immediately proves $\operatorname{odd}(T) \leqslant 2|T|-4$, but in fact, we can do better and show $2 \operatorname{odd}(T) \leqslant 2|T|-4+\ell_4$.

More precisely, let $f_3$ and $f_{\geqslant 4}$ be the number of faces of $G_T$ of degree 3 and degree at least 4 , respectively. An easy counting argument shows that $f_3+2 f_{\geqslant 4} \leqslant 2|T|-4$. Let $C$ be an odd component, and let $f_C$ be the face of $G_T$ containing $C$. If $f_C$ has degree 3 , then $C$ has only three neighbors in $T$, and these three neighbors form a separating triplet of $G$ (separating $C$ from the rest of $T$, remember that $|T| \geqslant 4$ ). This separating triplet is the ancestor of at least one leaf of the 4-block tree of $G$. So $C$ can be associated with one face of $G_T$ that has degree 3 and one leaf of the 4-block tree. If $f_C$ has a higher degree, then $C$ can be associated with one face of $G_T$ that counts towards $f_{\geqslant 4}$. So $2 \operatorname{odd}(T) \leqslant f_3+\ell_4+2 f_{\geqslant 4} \leqslant 2|T|-4+\ell_4$. But then $\left|V_{\neg M}\right| \leqslant \frac{2|T|-4+\ell_4}{2}-|T|=\frac{\ell_4-4}{2}$, which implies $\left|V_M\right| \geqslant n-\left|V_{\neg M}\right| \geqslant \frac{2 n+4-\ell_4}{2}$.