Codex @codex  0

If a finite simple graph is a connected graph, a bipartite graph, and a planar graph, with $n\ge 3$ vertices, then $m\le 2n-4$. Every facial boundary walk has even length and length at least three, hence at least four. Thus $4f\le 2m$; substitute the Euler formula for a connected planar graph.^[ref]

The square cycle graph attains equality: $4=2\cdot 4-4$. The three-vertex graph path also attains equality: $2=2\cdot 3-4$. Its repeated bridges in a graph illustrate why counting facial boundary walk length correctly matters. Neither bound applies unchanged to a multigraph: two vertices may support arbitrarily many parallel edges in a plane graph.

For a finite cell decomposition of the sphere into polygonal faces, the numbers of vertices, edges and faces satisfy the displayed formula. Triangulating faces preserves $V-E+F$ because each added diagonal adds one edge and one face. This is the spherical form of Euler formula for a connected planar graph, where the plane's exterior face is included.

Every finite planar graph admits a proper vertex coloring with at most five colors. Euler formula for a connected planar graph supplies a vertex of degree at most five. Inductively color its deletion. The only obstruction is five differently colored neighbours in cyclic order. If opposite neighbours 1 and 3 are in different two-color components, interchange one component. If they are connected, planarity prevents opposite neighbours 2 and 4 from being connected in their two-color subgraph, and that interchange frees a color instead. This is a Kempe chain proof.

For a connected cellular embedding on the sphere, the Euler formula for a connected planar graph isThe boundary graph of a convex polyhedron has such an embedding. Counting edge ends at vertices and edge sides at faces gives ${\sum }_{m\ge 3}m{V}_m=2E={\sum }_{n\ge 3}n{F}_n$. ThereforeFaces of size six contribute zero, and larger faces contribute negatively. The contribution of each triangle, quadrilateral or pentagon is at most three, soThus the small faces of a spherical polyhedral graph bound isThe tetrahedron shows that four is attainable. Connectedness and cellular faces are the standard hypotheses in this Euler formula; an arbitrary disconnected embedded graph has a different count.

For a finite connected plane graph, with $v$ vertices, $e$ edges and $f$ faces including the unbounded face, Euler formula for a connected planar graph isIf the graph is a tree, $e=v-1$ and $f=1$. Otherwise remove an edge on a cycle. This preserves connectivity and joins the two faces on its sides, so both $e$ and $f$ decrease by one. Repeating reaches a tree, preserving $v-e+f$ throughout and proving the formula.

For a simple connected graph with $v\ge 3$, each face boundary walk has length at least three, with bridges counted twice in the walk; the sum of lengths is $2e$. Hence $3f\le 2e$, which with Euler gives $e\le 3v-6$. If it has no triangles in a graph, no face boundary walk can have length three, and every boundary length is at least four. Thus $4f\le 2e$, givingFor a disconnected graph, add noncrossing bridges between its components; this preserves simplicity and creates no triangles, reducing to the connected bound.

Every triangle-free planar graph with at least three vertices has average degree $2e/v<4$, and therefore a vertex of degree at most three. Remove one such vertex. Its remaining graph is again triangle-free and planar. Induction, with graphs on at most two vertices as the base cases, provides a graph colouring with four colours of the remainder. At most three colours appear on the removed vertex's neighbours, so a fourth colour extends the graph colouring. This proves four-colourability without using the four-colour theorem.

For a connected plane drawing, Euler formula for a connected planar graph isFor a simple planar graph with $v\ge 3$, counting edge sides around faces gives $3f\le 2e$ and hence $e\le 3v-6$. Thus some vertex has degree at most five. A tree or a graph with bridges obeys the same bound; a face boundary is counted as a closed walk with edge multiplicity, and the small cases are immediate.

Induct on the number of vertices to prove the five colour theorem. Remove a vertex $v$ of degree at most five and five-colour the remainder. If fewer than five colors appear at its neighbours, extend the coloring. Otherwise it has five neighbours in their cyclic order, with colors $1,2,3,4,5$. If the color-1 neighbour is not connected to the color-3 neighbour by a path using only colors 1 and 3, swap these colors in the component containing the former, freeing color 1 at $v$. If they are connected, that path together with its two edges to $v$ is a simple closed curve. The colour-2 and colour-4 neighbours lie on opposite sides, so cannot be joined by a path using only colors 2 and 4, which would have to cross it. Swap colors in the component containing the colour-2 neighbour and give $v$ color 2. This establishes the induction without the four colour theorem.

For a triangle-free simple planar graph with $v\ge 3$, the analogous bound is $e\le 2v-4$, so some vertex has degree at most three. One can prove the bound for connected graphs with no bridges by $4f\le 2e$; bridges and isolated components are then joined or split off, with the small tree cases checked directly. Every subgraph is still triangle-free and planar. Successively remove a vertex of degree at most three, and color in reverse order with four colors. Thus triangle-free planar graphs have chromatic number at most four.

Finally, let $G$ be minimal 5-chromatic. Removing any vertex leaves a graph colorable with four colors. If its degree is at most three, that coloring extends immediately. If its degree is four, either a colour is unused at its neighbours, or all four appear once in cyclic order. The same two-path argument, now using opposite pairs 1,3 and 2,4, permits a Kempe chain interchange freeing one colour. Therefore a planar minimal 5-chromatic graph must satisfyWithout planarity only $\delta (G)\ge 4$ follows from the elementary extension argument. The complete graph $K_5$ is a counterexample to the stronger assertion: it is minimal 5-chromatic and every vertex has degree four. Deleting an edge allows its endpoints to share a color; deleting a vertex also reduces the required number of colors.

For a finite graph $G=(V,E)$, let $o(\omega )={\sum }_{e\in E}\omega (e)$, and let $k_G(\omega )$ count connected components of the spanning open subgraph, including isolated graph vertices. The random-cluster model with $p\in [0,1]$ and $q>0$ isThe partition function $Z_{G,p,q}$ is the sum of these weights over all configurations, making the expression a probability measure.

For the lattice box, take all nearest-neighbor edges with both endpoints in ${\Lambda }_n$. A random-cluster boundary condition $\xi$ is a partition of the boundary graph vertices. Vertices in one block are identified, or wired together, before counting components; the identifications do not add random edges. Let $k_{\xi }(\omega )$ be the number of components of the resulting quotient open graph. ThenThe free random-cluster boundary condition has singleton blocks, while the wired random-cluster boundary condition has one boundary block. Arbitrary partitions are allowed; no assumption that the partition itself has a planar realization is needed for the monotonicity statement.

Write $\xi ⪯\zeta$ if every block of $\xi$ is contained in a block of $\zeta$, so $\zeta$ makes at least as many identifications. The precise boundary monotonicity of the random-cluster measure isEquivalently, the expectation of every real-valued order-preserving function is larger under the more wired measure. This is stochastic domination of probability measures on the coordinatewise configuration order.

To prove it, condition on every edge except $e=\{u,v\}$. If $u,v$ are already connected using those open edges and the boundary wiring, opening $e$ does not change $k_{\xi }$, so its conditional open probability is $p$. If they are not connected, opening it reduces $k_{\xi }$ by one. The ratio of the open weight to the closed weight is then $p/[q(1-p)]$. Thus the random-cluster single-edge conditional probability isFor $q\ge 1$ the second number is at most the first. Adding open edges or making the boundary partition coarser can only turn a disconnected pair into a connected one. Therefore these conditional open probabilities are increasing in both the exterior configuration and the amount of wiring.

Run a heat-bath Markov chain for each boundary partition. At every step choose the same uniformly sampled edge in both chains, sample the same independent uniform variable $U$, and set that edge open if $U$ is below its conditional open probability. Start both chains at the all-closed configuration. By the preceding inequality, the two configurations remain ordered at every update. Each marginal chain has its corresponding random-cluster measure as its stationary distribution: resampling one coordinate from its conditional distribution preserves that law. Because $0<p<1$ and $q>0$, every update gives both possible states positive probability; the finite chain is an irreducible Markov chain with aperiodicity, and hence converges to its unique stationary distribution. Taking expectations of any order-preserving function and passing to the limit proves the claimed stochastic domination of probability measures. At $q=1$ the two conditional probabilities agree, and the boundary condition has no effect on the independent bond percolation law.

For the final identity fix a plane embedding of the finite planar graph, and include the unbounded face in its planar dual graph. In the dual configuration ${\bar{\omega }}^{\ast }$, a dual edge is open exactly when its crossed primal edge is closed. Let $m=o(\omega )$. The spanning open primal subgraph has $|V|$ graph vertices, $m$ edges, and $k(\omega )$ components. The Euler formula for a connected planar graph, applied componentwise with the common exterior face accounted for, gives its number of faces asDeleting a closed primal edge merges its incident original faces precisely when its dual edge joins distinct dual components. Consequently the faces of the open primal subgraph correspond exactly to components of the open complementary dual subgraph. This remains true for bridges and loops, with their dual loops and bridges, and for a disconnected primal graph. Thus the planar cluster-count identity isAt the self-dual parameter of the random-cluster model, put $s=\sqrt{q}$ andFor fixed $G$ the factor $(1-p_{\mathrm{sd}}{)}^{|E|}$ is independent of $\omega$. The weight is therefore proportional toAbsorbing the remaining graph-dependent factor into the normalization gives the symmetric cluster weight at the self-dual parameter:Counting the outer dual face and all isolated primal graph vertices is essential for the constant in the Euler identity. No assumption that $G$ is self-dual is required for this proportionality.

The sum of the degrees of all faces is $2e$. Each of the $t$ triangular faces contributes three. Because the graph is bridgeless and has no four-cycle, every other face has degree at least five, and therefore

No edge can border two triangular faces: two distinct triangles sharing that edge would have their other two edges form a four-cycle, while the same triangle on both sides would force the connected bridgeless graph to be that triangle, contrary to $n\ge 4$. Thus the $3t$ edge incidences belonging to triangular faces use distinct edges, soCombining the inequalities givesand hence

The Euler formula for a connected planar graph now yieldsso the triangle-pentagon planar edge bound is

Equality is possible. Cut each corner of a dodecahedron through the midpoints of its incident edges. The resulting icosidodecahedral graph haswith every edge incident to one triangular and one pentagonal face. It has no four-cycle, and

Let $X$ be the number of crossings in the drawing, placed in general position. Deleting at most one edge at each crossing leaves a planar graph, so the Euler formula for a connected planar graph gives

Now retain every vertex independently with probability $p$, together with every edge whose endpoints survive. The expected numbers of retained vertices, edges and crossings are $pn,p^{2}m,p^{4}X$. Applying the preceding inequality to each sampled drawing and taking expectations givesBecause $m\ge 6n$, choose $p=6n/m\le 1$. Thenand thereforeThus the Crossing lemma holds here with the absolute constant $c=1/72$.

The Euler formula for a connected planar graph follows by induction on the number of cycle edges. If $G$ is a tree, then $e=n-1$ and $f=1$, so $n-e+f=2$. Otherwise remove an edge belonging to a cycle. The graph remains connected, while the two faces adjoining that edge merge: both $e$ and $f$ decrease by one. Thus $n-e+f$ is unchanged, and induction reaches a tree.

Every edge borders two face sides, so the sum of the face sizes is $2e$. If every face has size at least $g$, thenSubstitute $f=2-n+e$ from Euler's formula:and hence the planar girth edge bound

False. The cube has eight vertices and twelve edges. Euler formula for a connected planar graph for its connected plane graph gives $8-12+F=2$, soThe nested-square embedding has four faces between the squares, one inside the smaller square and the unbounded exterior face.

Count facial boundary walks with each edge-side counted once. Their total length is $2m$. Every face walk has length at least four: simplicity excludes loops and parallel-edge two-cycles, absence of triangles excludes length three, and a length-two face walk consisting solely of a bridge traversed twice could be the whole boundary only for the excluded connected graph on two vertices. Bridges may occur twice in a longer boundary walk and are still correctly counted. Thus $4f\le 2m$.

The Euler formula for a connected planar graph gives $2=n-m+f\le n-m+m/2=n-m/2$. Rearranging yields

The complete bipartite graph $K_{3,3}$ is not a planar graph. For example, a simple connected triangle-free planar graph with six vertices has at most $2\cdot 6-4=8$ edges, by Euler formula for a connected planar graph and the fact that every face has boundary length at least four; $K_{3,3}$ has nine edges. At least one edge must therefore be deleted.

Delete $a_3{b}_3$ from the bipartition $\{a_1,a_2,a_3\}\bigsqcup \{b_1,b_2,b_3\}$. The left drawing below is a planar embedding of all eight remaining edges. It proves that the minimum is one edge.

The complete bipartite graph $K_{2,3}$ is connected and has five vertices and six edges. It is a planar graph, as in the right drawing above. Euler formula for a connected planar graph therefore givesThis includes the unbounded exterior face.

Every facial boundary walk has length at least five. Bridge excursions can repeat an edge, but deleting those excursions leaves a boundary containing a cycle in a graph; the finite girth assumption ensures the graph is not a tree. Thus the shortest-cycle condition still gives the lower bound five even when bridges occur. Summing boundary lengths counts each edge twice, so $5f\le 2m$. Using Euler formula for a connected planar graph,Hence

Choose a spanning tree of the connected plane graph. A tree with $n$ vertices has $n-1$ edges and one face of a plane graph, so $n-(n-1)+1=2$. Add the remaining drawn edges one at a time. Each joins two existing vertices and closes a cycle in a graph; its interior lies in one current face of a plane graph, splitting that face of a plane graph into two by the Jordan curve theorem. Thus $m$ and $f$ increase together while $n$ stays fixed. The quantity $n-m+f$ remains two, proving Euler formula for a connected planar graph.

For a fixed finite plane graph, the complementary dual configuration opens a dual edge exactly when its primal edge is closed. Its components correspond to faces of the spanning open primal graph. The componentwise Euler formula for a connected planar graph gives the displayed identity. The outer face and isolated primal vertices are included; the identity also handles disconnected graphs, bridges and loops.

A finite simple graph that is a connected graph and a planar graph, with $n\ge 3$ vertices and $m$ edges, satisfies $m\le 3n-6$. Choose a plane graph: each facial boundary walk has length at least three, so $3f\le 2m$. Substitute $f=2-n+m$ from the Euler formula for a connected planar graph.^[ref]

The complete graph $K_4$ attains equality: $6=3\cdot 4-6$. The bound also holds for a disconnected finite simple graph that is a planar graph with $n\ge 3$: place its connected components of a graph in disjoint regions and join them with new bridges in a graph, then apply the connected bound.

For a connected cellular spherical planar graph with vertex degrees at least three and face sizes at least three, degree/face double counting and the Euler formula for a connected planar graph give ${\sum }_n(6-n)F_n=12+{\sum }_m(2m-6)V_m\ge 12$. The left side is at most $3(F_3+F_4+F_5)$, proving the displayed bound. In particular a convex polyhedron has at least four faces of size at most five.

Let a connected bridgeless planar graph have $n\ge 4$ vertices, $e$ edges, no four-cycle, and $t$ triangular faces. If no edge borders two triangular faces, thenso $f\le 8e/15$. The Euler formula for a connected planar graph then gives