In the following paper, Hudák Dávid, and Tomáš Madaras give the following Theorem 1.1.
- Hudák, Dávid, and Tomáš Madaras. "On local properties of 1-planar graphs with high minimum degree." Ars Mathematica Contemporanea 4.2 (2011): 245-254.
Theorem 1.1. Each 1-planar graph of minimum degree 7 contains
a) a pair of adjacent 7-vertices,
b) a copy of $K_4$ with all vertices of degree at most 13,
c) a copy of $K_{2,3}^*$ with all vertices of degree at most 13 ,
d) a copy of $W_5$ with all vertices of degree at most 11.
The authors mainly use the charging and discharging method to prove that a 1-planar graph with minimum degree 7 contains certain structures. I will use b) to illustrate, and excerpt the proof of theorem b).
Proof of Theorem 1.1b). By contradiction. Suppose that there exists a 1-planar graph $G$ of minimum degree 7 such that each its subgraph $K_4$ contains at least one $\geq 14$-vertex, called big; vertices of degrees between 7 and 13 are called intermediate. We proceed with the Discharging Method with the initial charge assignment (2); the initial charges are redistributed according to following rules:
Rule 1: Each $\geq$ 4-face $\alpha \in F^{\times}$redistributes its initial charge uniformly among incident 4-vertices.
Rule 2: Each intermediate vertex sends $\frac{1}{7}$ to each adjacent 4-vertex.
Rule 3: Let $[x y z]$ be a 3-face of $G^{\times}, x$ be a 4-vertex and $y$ be an intermediate vertex. Then $y$ sends additional $\frac{1}{14}$ to $x$.
Rule 4: Each big vertex sends $\frac{4}{7}$ to each adjacent 4-vertex.
Rule 5: Let $[x y z]$ be a 3-face of $G^{\times}, x$ be a 4-vertex and $y$ be a big vertex. Then $y$ sends additional $\frac{2}{7}$ to $x$.
We check the nonnegativity of final charges of vertices and faces of $G^{\times}$. From the formulation of discharging rules, it is easy to see that the final charge of all faces is nonnegative. Thus, it is enough to analyze just the final charge of vertices.
Case 1: Let $x$ be a 4-vertex of $G^{\times}$. If $x$ is incident with at least two $\geq 4$-faces, then, by Rule $1, c^*(x) \geq-2+2 > \cdot \frac{2 \cdot 4-6}{2}=-2+2 \cdot 1=0$. If $x$ is incident with exactly one $\geq 4$-face, then, by Rules 1, 2 and 3 (or, eventually, 1, 4 and 5) we obtain the estimation $c^*(x) \geq-2+\frac{2 \cdot > 4-6}{2}+4 \cdot \frac{1}{7}+6 \cdot \frac{1}{14}=0$. Finally, if $x$ is incident only with 3 -faces, then its neighbours in $G^{\times}$induce a $K_4$, hence, one of them is big; then, by Rules 2,3,4 and 5, we obtain $c^*(x) \geq-2+3 \cdot \frac{1}{7}+6 \cdot > \frac{1}{14}+\frac{4}{7}+2 \cdot \frac{2}{7}=0$.
Case 2: Let $x$ be an intermediate $d$-vertex of $G^{\times}$. Then $c^*(x) \geq d-6-d \cdot \frac{1}{7} \geq 0$ for $d \geq 7$.
Case 3: Let $x$ be a big $d$-vertex of $G^{\times}$. Then $c^*(x) \geq d-6-d \cdot \frac{4}{7} \geq 0$ for $d \geq 14$.
The charging and discharging method is very clever, but also very elusive. I really can't think of an intuitive reason why a 1-planar graph with minimum degree 7 must contain $K_4$.
Do we have any hope of proving this fact without using the charging and discharging method?
