Lagmental Vicfred

Triangle-Free Planar Graphs Have an Even Stronger Bound by Vicfred

tags: mathematics, planar graphs, coloring, duality

When every face has length at least four, a planar graph has at most two n minus four edges. I want the notation, the mechanism, and the failure mode visible at the same time.

Objects and notation

A planar embedding divides the sphere into vertices, edges, and faces. Euler's relation \(|V|-|E|+|F|=2\) constrains density, while the dual \(G^\ast\) records adjacency of faces.

$$ G\ \text{simple, planar, triangle-free},\qquad|V|\ge3 $$

I keep the defining relation \(\mathsf D\) above the derived relation \(\mathsf C\). This exposes whether cancellation used \(x\ne0\) and whether the conclusion is canonical.

$$ |E|\le2|V|-4 $$

Push the symbols

The computation below is not a second theorem. It is a checksum for the definitions and a place to inspect the difficult LaTeX at full size.

$$ 2|E|=\sum_f\deg(f)\ge4|F|\Longrightarrow2\le|V|-\frac{|E|}{2} $$

Structural reading

The two-row display is also a debugging tool: if the conclusion changes when only notation changes, some hidden choice has entered the argument.

$$ \begin{aligned} \mathsf{D}\;&:\quad G\ \text{simple, planar, triangle-free},\qquad|V|\ge3,\\[5pt] \mathsf{C}\;&:\quad |E|\le2|V|-4. \end{aligned} $$

A hypothesis worth keeping

Planarity is a property of a graph, while a plane graph includes a chosen embedding. The dual depends on that embedding.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] |E|\le2|V|-4 \end{gathered}} $$

This is enough machinery for one note: an exact object, a worked case, a structural law, and a clearly marked boundary. Each layer can now be tested independently.

This article was posted on Thu 25 July 2013. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.