I have read the following article in which the authors briefly prove that the lower bound on the matching number of a maximal planar graph is $\frac{n+8}{3}$.
- Biedl, T., & Wittnebel, J. (2023). Large Matchings in Maximal 1-planar graphs. arXiv preprint arXiv:2301.01394.
I didn't understand one of the steps in the proof below.
I can only get
$$ \begin{align} \operatorname{comp}(G\setminus S)-|S|&=\sum_df_d^\odot-|S|\\ &=\sum_df_d^\odot-\big(\frac{\sum_d(d-2)f_d+4}{2}\big)\\ &=\sum_df_d^\odot-\big(\frac{\sum_d(d-2)f_d}{2}\big)-2. \end{align} $$
Why did the authors get $\operatorname{comp}(G\setminus S)-|S|\le \frac{1}{2}f^\odot_3-2$?
Thank you for the response from Misha Lavrov. I think it is necessary to clarify some concepts. I will first excerpt some necessary definitions from the article as follows.
Eidts: The face-boundary is the boundary of F, viewed as a collection of circuits in the graph (some of those circuits may consist of just one vertex, or of a single edge visited twice).
Define the degree $\deg(F)$ of $F$ to be $m_F+2 \operatorname{comp}(F)-2$, where $m_F$ is number of edge-incidences in the face-boundary (repeatedly visited edges count twice).
Therefore, for a face bounded by an isolated vertex, its degree is $0+2\times 1-2=0$. For a face bounded by an edge, its degree is $2+2\times 1-2=2$. For a face bounded by two isolated vertices, its degree is $0+2\times 2-2=2$.
For example, considering the following maximal planar graph with 16 vertices. If we choose $S=\{v\}$, then we $f_0^\odot$ will appear in $\Gamma (S)$. Now $\operatorname{comp}(G\setminus S)-|S|=1-1=0>0-2$ (since $f_3^\odot =0$).
Similarly, if we choose $S=\{u,v\}$, then $f_2^\odot$ will appear in $\Gamma (S)$.Now $\operatorname{comp}(G\setminus S)-|S|=1-2=-1>0-2$ (since $f_3^\odot =0$).
The first source of an inequality rather than an equation comes from applying $f_d^\odot \le f_d$ to every term of the second sum: $$ \operatorname{comp}(G \setminus S) - |S| \le \sum_d f_d^\odot - \frac{\sum_d (d-2) f_d^\odot}{2} - 2. $$ We can now simplify this to $$ \operatorname{comp}(G \setminus S) - |S| \le \sum_d (2 - \tfrac d2)f_d^\odot - 2. $$
For $d \ge 4$, the coefficient on $f_d^\odot$ is non-positive, and we can drop all those terms in the inequality. Degree-$1$ faces are impossible, and if degree-$0$ and degree-$2$ faces do not exist, then $\frac12 f_3^\odot$ is the only term left; this gives us the desired $$ \operatorname{comp}(G \setminus S) - |S| \le \frac12 f_3^\odot - 2. $$ As pointed out in the question, the inequality is false if there is a degree-$2$ face, so we do have to worry about $f_0^\odot$ and $f_2^\odot$ terms. However, such faces are very limited.
The paper defines the degree of a face $F$ to be $m_F + 2 \text{comp}(F)-2$, where $m_F$ is the usual face length (counting edges double if $F$ is on both sides of the edge) and $\text{comp}(F)$ is the number of components of $F$. Therefore:
In each of these cases, $\operatorname{comp}(G \setminus S) - |S|$ is either $0$, $-1$, or $-2$. In the end, we want to show that $\operatorname{comp}(G \setminus S) - |S| \le \frac{n-8}{3}$, which holds in all cases where degree-$0$ or degree-$2$ faces appear.