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.

A chordal graph is a finite simple graph with no induced cycle of length at least four. Equivalently, every cycle in a graph with at least four vertices has a chord: an edge joining two nonconsecutive vertices of that graph cycle. The word "induced" matters: the induced subgraph on the chosen vertices must contain exactly the cycle's edges, with no chords. Triangles are allowed. This definition concerns adjacency, independently of how the graph is drawn.

For the square cycle graph $C_4$, take vertex set $\{a,b,c,d\}$ and set of edges $\{ab,bc,cd,da\}$, where $ab$ abbreviates $\{a,b\}$. Its graph neighbourhoods are $N(a)=N(c)=\{b,d\}$ and $N(b)=N(d)=\{a,c\}$. The square is an induced cycle, so $C_4$ is not a chordal graph. Add the single edge $ac$: now $N(a)=\{b,c,d\}$, $N(b)=\{a,c\}$, $N(c)=\{a,b,d\}$, and $N(d)=\{a,c\}$. The only possible four-vertex graph cycle has chord $ac$, so this new graph is a chordal graph. Its maximal cliques are exactly $\{a,b,c\}$ and $\{a,c,d\}$.

Connect these two maximal cliques by a single edge labelled with their intersection $\{a,c\}$. The result is a junction tree, also called a clique tree: its nodes are maximal cliques, and the nodes containing any fixed original vertex induce a connected graph inside the tree. Here $a,c$ occur in both nodes, while $b,d$ each occur in just one. This is the running intersection property. More generally, a nonempty connected graph is a chordal graph exactly when its maximal cliques admit such a tree; a disconnected chordal graph can be represented by one such tree per connected component of a graph.^[ref]

A chordal graph need not be a planar graph: the complete graph $K_5$ is a chordal graph, since every pair of distinct vertices is adjacent, but its ten edges violate the planar graph edge bound $|E|\le 3|V|-6=9$. Conversely, even a plane drawing whose bounded faces are triangles can hide an induced cycle: a wheel graph with a four-vertex rim and a central vertex joined to the whole rim still has the rim as an induced cycle. Adding chords to obtain a chordal graph is called triangulation of an undirected graph; this is an adjacency condition, rather than a requirement about planar faces.

Why is this structure useful? The maximal cliques collect local interactions, and the running intersection property makes their overlaps sufficient for consistent communication. For random variables $x_a,x_b,x_c,x_d$ with finite state sets, a probabilistic graphical model of the square-plus-diagonal form can havewhere the two nonnegative clique potentials have a positive normalizing constant $Z$. Eliminating $x_b$ produces the two-variable junction-tree sum-product messageThe shared clique $\{a,c\}$ carries everything needed from the eliminated side. For $q$ possible states per random variable, this example uses two sums over $q^3$ configurations after reusing the message, rather than directly summing over $q^4$ configurations. The example's message is an exact finite sum, with no simulated data. Large maximal cliques still make exact inference expensive; chordal graphs provide a decomposition, not a universal guarantee of cheap inference.^[ref]

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.

Every finite planar graph has chromatic number at most four. This stronger theorem is distinct from the elementary five colour theorem; the latter's Kempe chain proof does not prove this assertion.

On vertices $0,\dots ,7$, join cyclic indices differing by one or two modulo eight. The resulting planar graph has a square face bounded in order by $0,2,4,6$. Deleting at most three vertices cannot disconnect it: each break in the surviving cyclic chain requires two consecutive deleted vertices, and two separate breaks require four deletions. It is therefore four-connected. Disjoint paths joining $0$ to $4$ and $2$ to $6$ would cross in the complementary disk of the square face, contrary to the Jordan curve theorem. Thus four-connectivity does not guarantee two-linkage.

A graph minor compresses connected regions of a graph into single vertices while retaining selected connections between them. For finite simple graphs, $H\preccurlyeq G$ means that some sequence of deleting vertices, deleting edges, and performing edge contractions produces $H$ up to graph isomorphism. Deleting a vertex also deletes all its incident edges; deleting an edge leaves its endpoints. The edge contraction convention here removes resulting self-loops and duplicate edges.^[ref]

For an exact small example, let $G$ be the cycle graph $C_4$ with vertices $u,v,a,b$ and edges $uv,va,ab,bu$. Contract $uv$ to a new vertex $w$. The surviving edges are $wa,ab,bw$, giving the complete graph $K_3$. Thus $K_3\preccurlyeq C_4$, although $C_4$ has no triangle in a graph as a subgraph. The branch sets of a graph minor are $\{u,v\},\{a\},\{b\}$, with the original edges $va,ab,bu$ witnessing all three required adjacencies. The first panel of the edge contraction diagram shows this operation.

A subgraph uses existing vertices and edges; a topological minor permits a graph subdivision of the target as a subgraph, so target edges become graph paths with mutually disjoint interiors and no target vertex in an interior. An ordinary graph minor permits whole connected branch sets of a graph minor in place of target vertices. Every topological minor is a graph minor, by contracting the replacement graph paths.^[ref]

The converse fails. Take the tree with edges $uv,ua,ub,vc,vd$. Contracting $uv$ gives the star graph $K_{1,4}$. Yet the original tree has maximum degree three, whereas every graph subdivision of $K_{1,4}$ retains a centre of degree of a vertex four. Hence $K_{1,4}$ is a graph minor but not a topological minor of this tree. The difference is that a connected branch set of a graph minor may gather connections incident to several original vertices.

The counts of vertices and edges never increase under these operations. However, the $C_4$ example shows that being a bipartite graph is not preserved: its graph minor $K_3$ contains an odd cycle. Its chromatic number also increases from two to three. A connected graph stays connected under an edge contraction, because the image of each graph path still connects its endpoints, but deletion can disconnect it. Thus one must check the particular graph property before treating it as preserved by taking graph minors.

Being a planar graph is preserved: in a crossing-free drawing, shrink a contracted edge and bring its incident edges into the merged vertex; deletion merely removes parts of the drawing. This makes a nonplanar graph minor a certificate that the original graph is nonplanar. More strongly, for a finite simple graph, being a planar graph is equivalent to having neither the complete graph $K_5$ nor the complete bipartite graph $K_{3,3}$ as a graph minor. Finding the corresponding branch sets of a graph minor settles nonplanarity even when no literal $K_5$ or $K_{3,3}$ subgraph is present. The converse is a substantial theorem, rather than a consequence of preservation alone.^[ref]

A graph subdivision $TH$ replaces each edge $uv$ of a simple graph $H$ by a graph path of at least one edge joining its original endpoints. The original vertices are branch vertices of a graph subdivision. The replacement graph paths have pairwise disjoint interiors, contain no branch vertices of a graph subdivision internally, and together make up the entire new graph. Leaving an edge unchanged is allowed.^[ref]

For an explicit example, take $H$ with vertex set $\{A,B,C,D\}$ and edges $AB,BC,CA,AD$: a triangle in a graph with one attached leaf of a graph. Replace its edges by the following branch paths of a graph subdivision:The resulting graph subdivision $S$ has vertex set $\{A,B,C,D,x,y,z\}$ and edges $Ax,xB,By,yz,zC,CA,AD$. The internal vertex sets are $\{x\},\{y,z\},\varnothing ,\varnothing$, so disjointness is explicit. The degrees of vertices of $A,B,C,D$ remain $3,2,2,1$, respectively; the three new internal vertices each have degree of a vertex two.

Adding $m$ internal vertices to a finite graph increases both its vertex count and its edge count by $m$. Here $m=3$, so four vertices and four edges become seven of each; the graph excess is unchanged. Each replacement graph path remains a route between the same junctions. Thus graph subdivision preserves whether a graph is a planar graph: insert intermediate vertices along a crossing-free drawing, or trace each replacement graph path as one edge to recover a drawing of the original graph. Travel times or capacities are separate modelling choices and are not determined by this adjacency construction.

The honeycomb lattice is the periodic degree-three planar graph consisting of the vertices and edges of a regular hexagonal tiling. It has two vertex classes; every edge joins opposite classes. Its planar dual graph is the triangular lattice.

A finite simple graph is a planar graph if and only if it contains no graph subdivision of the complete graph $K_5$ or the complete bipartite graph $K_{3,3}$ as a subgraph; equivalently, neither is a topological minor. The easy direction follows by tracing each replacement graph path as one drawn edge. The converse asserts that every failure of planarity contains one of these two patterns.^[ref]

Graph Theory by Reinhard Diestel (Planar Graphs preview, §4.4, Theorem 4.4.6, printed p. 111) dates Kuratowski's theorem to 1930 and the equivalent graph minor characterization to 1937. These dates are that textbook's historical attribution.

The martini lattice is obtained from the honeycomb lattice by replacing every vertex in one of its two vertex classes by a triangle, attaching its three former incident bonds to the triangle's three vertices. It is a periodic degree-three planar graph, with triangular faces and nine-sided faces. Each decorated vertex and its incident bonds is a three-terminal cell with three internal triangle bonds and three terminal spokes. Its independent bond percolation threshold is $1/\sqrt{2}$, as follows from three-terminal cell partition duality.

The complete graph $K_5$ has $n=5$ and $m=\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$, exceeding the planar graph edge bound $3\cdot 5-6=9$. Therefore it is not a planar graph. The complete bipartite graph $K_{3,3}$ has $n=6$ and $m=3\cdot 3=9$. The general bound allows twelve edges, but the bipartite planar graph edge bound allows only eight, proving nonplanarity.

These are necessary bounds, not a complete planarity test. For an original counterexample, subdivide every edge of $K_{3,3}$ once. The resulting simple graph is a connected graph with $n=15$, $m=18$, and is bipartite: put all original vertices in one part and all nine new vertices in the other. Both inequalities hold, $18\le 39$ and $18\le 26$. Nevertheless, a crossing-free graph drawing would let us trace each two-edge graph path as one curve, producing an impossible embedding of $K_{3,3}$. The graph subdivision preserves this obstruction. Kuratowski's theorem supplies a stronger characterization than these counts.

A self-avoiding walk of length $n$ is a sequence of $n+1$ distinct graph vertices joined consecutively by edges. Split a rooted self-avoiding walk of length $m+n$ after $m$ steps. There are ${\kappa }_m$ possible prefixes; each remaining segment is a self-avoiding $n$-step walk from its current graph vertex, and forbidding intersections with the prefix can only reduce its count below ${\kappa }_n$. Translation invariance therefore givesApply the Fekete lemma, proved in Question 4(a), to $\log {\kappa }_n$. It gives $\log \mu ={\inf }_n{n}^{-1}\log {\kappa }_n$ and hence existence of the connective constant. Walks using only the $d$ positive coordinate directions never revisit a graph vertex, so there are at least $d^n$. A walk has $2d$ choices for its first step and at most $2d-1$ subsequently because immediate reversal is forbidden. Thus

For independent bond percolation, let $C(0)$ be the percolation cluster of the origin, $\theta (p)=P_p(|C(0)|=\infty )$, and $p_c=\inf \{p:\theta (p)>0\}$. An infinite percolation cluster in a locally finite graph contains an open self-avoiding path of every length. The union bound givesWhen $p\mu <1$, the right-hand side tends to zero, since its $n$th root tends to $p\mu$. Hence the connective-constant lower bound for percolation is

For the upper bound in two dimensions, use the square planar dual graph. Call a dual edge available when its crossing primal edge is closed. Each dual edge is available with probability $q=1-p$, independently. The planar graph boundary lemma says that a finite primal percolation cluster is enclosed by a graph cycle consisting of such edges: its external edge boundary gives this graph cycle. We show that $q\mu <1$ guarantees positive percolation probability.

Let $N_n$ count enclosing graph cycles of length $n$. Because the origin lies inside their coordinate bounding box and their diameter is at most $n$, every such graph cycle has a graph vertex within a box of side $2n+3$. From each possible root, the first $n-1$ edges give a self-avoiding walk; the final closing edge is then determined. Dropping the closure restriction gives the convenient boundChoose $\rho$ with $q\mu <\rho <1$. The connective-constant limit of a sequence implies ${\kappa }_{n-1}{q}^n\le C{\rho }^n$. Consequently the large-circuit tailis summable.

Condition all primal edges inside a large square $[-L,L{]}^2$ to be open; this event has positive probability. The origin percolation cluster then contains that square. If it is finite, its enclosing graph cycle has length at least $L$. A proposed graph cycle using a pinned-open edge now has conditional probability zero; every other proposed graph cycle still has probability $q^n$ by independence of random variables. For $L$ large enough the union bound for the remaining graph cycles is less than one. There is therefore positive conditional probability that the origin percolation cluster is infinite. This proves the connective-constant Peierls bound without needing the exact value of $p_c$:

In bond percolation on ${\mathbb{Z}}^d$, edges are independently open with probability $p$ and closed otherwise. An open percolation cluster is a connected component using only open edges. In site percolation it is the graph vertices that are independently declared open. The percolation probability $\theta (p)=P_p(0\leftrightarrow \infty )$ measures the chance that the origin lies in an infinite percolation cluster, and the percolation critical probability is $p_c=\inf \{p:\theta (p)>0\}$. Monotone coupling of Bernoulli percolation by independent uniform distribution makes $\theta$ nondecreasing.

The sharpness of the percolation transition says that below $p_c$ connection probabilities on ${\mathbb{Z}}^d$ decay exponentially with distance, while above $p_c$ the percolation probability is positive. There is almost surely a unique infinite percolation cluster in the supercritical regime. On the square lattice, the Harris-Kesten theorem gives bond threshold $1/2$, and there is no infinite percolation cluster at percolation critical probability. The emergence of connections on arbitrarily large scales is the geometric meaning of the phase transition.

Several observables describe this singular behavior. The percolation susceptibility is $\chi (p)=E_p|C(0)|$ for $p<p_c$. A directional correlation length can be defined through exponential two-point decay, $\xi (p{)}^{-1}=-{\lim }_n{n}^{-1}\log P_p(0\leftrightarrow n{e}_1)$. Percolation critical exponents describe leading powers, conveniently defined logarithmically rather than requiring exact asymptotic amplitudes:The first limit of a sequence approaches from above, the other two from below. At percolation critical probability, percolation two-point connection probability is expected to have leading power $|x{|}^{-(d-2+\eta )}$, and the number per site of percolation clusters of size $s$ has leading power $s^{-\tau }$. This cluster-count probability distribution differs from the size-biased probability distribution seen by choosing a site. Scaling relations for critical exponents such as $\gamma =(2-\eta )\nu$ and $2\beta +\gamma =d\nu$ connect the exponents in their applicable scaling regime; hyperscaling relation is not valid above the upper critical dimension of percolation in ordinary mean-field regimes.

The percolation universality hypothesis predicts that dimension and large-scale symmetry, rather than microscopic graph details, determine these exponents and scaling functions. Thus square-lattice bond and triangular-lattice site models are expected to share the planar graph universality class despite different microscopic definitions. Universality does not mean identical critical probabilities, amplitudes or finite-lattice distributions. Exact values and existence of exponents require model-specific theorems, not merely this prediction.

Two dimensions have an additional structure: conformal maps preserve angles, and critical crossing probabilities are expected to be unchanged under conformal transport of the domain and its marked boundary arcs. A crossing probability then depends only on the conformal shape of that marked quadrilateral. The Cardy boundary crossing formula gives this dependence in terms of its boundary cross ratio. For critical triangular-lattice site percolation, conformal invariance and the resulting exponents are established; examples are $\beta =5/36$, $\gamma =43/18$, $\nu =4/3$, with the rigorous statements in leading-power form. These values are summarized in Smirnov and Werner's original paper. Their universality extension to arbitrary planar lattices should not be presented as the same theorem.

An exploration path separating the two colors, with opposite boundary colors on two arcs, has a domain Markov property of a percolation exploration: conditional on the explored portion, the unexplored colors retain their independent laws with the newly exposed boundary colors. Conformal invariance, this domain Markov property and suitable regularity lead to Schramm–Loewner evolution. In the upper half-plane its chordal equation iswhere $B_t$ is standard Brownian motion and time is normalized by half-plane capacity. Critical percolation corresponds to $\kappa =6$. Thus the complicated discrete interface becomes a conformally natural random curve driven by one real Brownian motion. Its crossing and arm probabilities supply critical exponents and, through scaling relations for critical exponents, near-critical singularities. This makes conformal methods predictive tools for the transition, rather than only descriptions of an interface's appearance.

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.

Euler characteristic for a finite connected plane graph is $v-e+f=2$. For a simple connected planar graph with $v\ge 3$, each facial boundary has length at least three and the total boundary length is $2e$, so $3f\le 2e$. Combining gives $e\le 3v-6$, and therefore average degree of a graph $2e/v<6$. Some vertex has degree at most five. Components of size one or two have this property directly, so every nonempty finite simple planar graph has $\delta (G)\le 5$.

Prove five colour theorem by induction on vertex count. Remove a vertex $x$ of degree at most five and colour the remaining planar graph with five colours. If its neighbours use fewer than five colours, assign an unused colour to $x$. Otherwise its five neighbours $x_1,\dots ,x_5$ occur in cyclic order around $x$ with colours $1,\dots ,5$. If no path of colours $1,3$ connects $x_1$ to $x_3$, interchange these colours in the component of $x_1$, freeing colour 1 at $x$.

If such a path exists, a simple path together with $x{x}_1$ and $x{x}_3$ makes a Jordan curve. The cyclic order puts $x_2$ and $x_4$ on opposite sides. A path of colours $2,4$ between them would have to cross the curve, impossible in the plane embedding; it cannot meet the differently coloured path or use the removed vertex. Interchange colours $2,4$ in the component of $x_2$, freeing colour 2 at $x$. The colouring extends in every case. Thus $\chi (G)\le 5$ for finite simple planar graphs. The usual simple-graph convention is needed: loops would invalidate a proper-colouring assertion.

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.

Let $G$ have $n$ vertices and $e$ edges. Its complement graph $\overline{G}$ hasedges. If both graphs were planar, the planar graph edge bound would giveEquivalently, $n^2-13n+24\le 0$, whose larger root is $(13+\sqrt{73})/2<11$. Thus an integer $n\ge 11$ is impossible, proving that

Now suppose that $G$ and $\overline{G}$ are both bipartite. In a bipartition $V(G)=A\bigsqcup B$, every pair within $A$ and every pair within $B$ is adjacent in $\overline{G}$. Since a bipartite graph contains no triangle, $|A|,|B|\le 2$, and hence $|V(G)|\le 4$. Equality is attained by the path $P_4$, whose complement is again a copy of $P_4$. Therefore the maximum order is

A 3-connected graph contains a cycle, and any cycle is a complete graph subdivision $T{K}_3$.

For $T{K}_4$, choose a cycle $C$ for which some $C$-bridge has at least three attachment vertices $a,b,c$; such a choice is always possible in a 3-connected graph. Indeed, every component outside a cycle has at least three attachments, since one or two would form a vertex cut, and if a chosen cycle is spanning, a chord can be used to choose a smaller cycle and expose the remaining bridge. In a minimal connected part of that bridge joining $a,b,c$, suppress degree-two vertices. The result has a branch vertex $w$ joined to $a,b,c$ by three paths whose interiors are mutually disjoint and avoid $C$. The three arcs of $C$ between $a,b,c$, together with these three paths, form a subdivision of the complete graph on branch vertices $w,a,b,c$. Hence

A 3-connected graph need not contain a $T{K}_5$. The complete graph $K_4$ itself is 3-connected and has only four vertices, so it cannot contain a graph subdivision of $K_5$. Equally, any planar 3-connected graph is a counterexample because a subdivision of the complete graph $K_5$ would be nonplanar.

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$.