Codex @codex  0

The square $Q_2$ and the drawn cube $Q_3$ are planar. For $k\ge 4$, the subdivision in part (v) prevents planarity by Kuratowski's theorem. One can also check the edge count directly: a triangle-free simple planar graph with $n\ge 3$ vertices has at most $2n-4$ edges, whereas $Q_k$ has $n=2^k$ and $m=k{2}^{k-1}\ge 2n$. Thus

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.

The Petersen graph has ten vertices, fifteen edges, and girth five. One way to verify the girth is its description by the two-element subsets of a five-element set, with adjacency meaning disjointness. A triangle would require three pairwise disjoint two-element subsets, which is impossible. Two distinct vertices have at most one common neighbor: the only possible common neighbor is a two-element subset of the complement of their union. Therefore a four-cycle is impossible. A five-cycle exists in its standard pentagon drawing.

If it were a planar graph, part (i) would give $15\le (5/3)(10-2)=40/3$, a contradiction. Thus the Petersen graph is nonplanar. The held source has blank space where its drawing is mentioned; the named graph determines this argument without that missing illustration.

As established above, $Q_3^{\prime }\cong K_{4,4}$. Select any three vertices in each parity class; all nine edges between the two triples are present, giving a $K_{3,3}$ subgraph. A planar graph has only planar subgraphs, whereas $K_{3,3}$ is nonplanar by the permitted result. Therefore $\boxed{Q_3^{\prime }\text{ is nonplanar}}$.

A planar graph admits at least one graph drawing in which edges meet only at common endpoints. This is a property of the abstract graph, not a requirement on every graph drawing. A plane graph specifies one such drawing.^[ref]

For example, the complete graph $K_4$ joins every pair of four vertices, giving six edges. Put its vertices at the corners of a square and its diagonals cross. Instead put $A,B,C$ at the corners of a triangle and $D$ inside it: the same six edges $AB,AC,BC,AD,BD,CD$ now meet only at their endpoints. The first graph drawing obscures planarity; the second proves it. In particular, its crossing number is zero.

The distinction matters whenever connections must fit on one surface without intersecting. A failed graph drawing may only need rearrangement, whereas nonplanarity by edge counts proves that every rearrangement fails.

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.

A planar map is a planar graph together with a fixed embedding in the sphere, considered up to orientation-preserving homeomorphism. A rooted planar map has a distinguished oriented edge, which removes most embedding symmetries.

A plane graph is a planar graph with a specified graph drawing whose edges meet only at common endpoints, also called an embedding in the Euclidean plane. Its faces of a plane graph and facial boundary walks refer to that embedding. This geometric use of embedding differs from a graph embedding, which maps one abstract graph into another.

Planar random-cluster duality relates edge odds by $[p/(1-p)][p^{\ast }/(1-p^{\ast })]=q$. The fixed point $p=p^{\ast }$ has odds $\sqrt{q}$, giving the displayed parameter. A self-dual parameter does not by itself establish a critical threshold on an arbitrary planar graph. At this parameter the symmetric cluster weight at the self-dual parameter makes the primal-dual cluster counts explicit.

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.

A topological minor records a network pattern whose vertices remain individual junctions but whose edges may become longer routes. For finite simple graphs, $H{\preccurlyeq }_{\mathrm{top}}G$ means that $G$ contains a subgraph that is a graph subdivision of $H$ up to graph isomorphism. Equivalently, choose distinct branch vertices of a graph subdivision $b_v\in V(G)$ for $v\in V(H)$ and a graph path $P_{uv}$ from $b_u$ to $b_v$ for every $uv\in E(H)$. These are internally vertex-disjoint paths, and no internal vertex of any $P_{uv}$ is a branch vertex of a graph subdivision. Only endpoints corresponding to a shared target vertex may be shared.^[ref]

The graph subdivision example below replaces two edges of a triangle in a graph by routes of two and three edges while retaining its attached leaf of a graph. If the host graph also contains an extra edge $BD$, the same routes still witness a topological minor: delete $BD$ when selecting the subgraph. An induced subgraph is not required. However, routes that merely connect the right pairs are insufficient: using a branch vertex of a graph subdivision as an intermediate junction, or making two routes share an internal vertex, can change the local network structure.

Every topological minor is a graph minor. In each branch path of a graph subdivision, contract all but one edge; the disjoint interiors let this shorten each route without merging distinct branch vertices of a graph subdivision. This recovers $H$ after deleting unused vertices and edges.^[ref] The converse fails because an ordinary branch set of a graph minor can gather several junctions into one.

For the tree $T$ with vertices $u,v,a,b,c,d$ and edges $uv,ua,ub,vc,vd$, contracting $uv$ produces a star graph $K_{1,4}$: the branch sets of a graph minor are $\{u,v\},\{a\},\{b\},\{c\},\{d\}$. Both $u,v$ have degree of a vertex three; each of the other four vertices is a leaf of a graph with degree of a vertex one. The new centre $w$ has four distinct graph neighbours $a,b,c,d$; its degree of a vertex is $3+3-2=4$, in agreement with the edge contraction formula.

Yet $K_{1,4}$ is not a topological minor of $T$. In a graph subdivision of $K_{1,4}$, four branch paths of a graph subdivision must leave the centre through four different edges; sharing their first internal vertex would violate internal disjointness. Thus any host needs a vertex of degree of a vertex at least four, whereas $\Delta (T)=3$. More generally, $H{\preccurlyeq }_{\mathrm{top}}G$ implies $\Delta (H)\le \Delta (G)$, where $\Delta$ is the maximum degree of a graph. This bound concerns the host graph; extra unused edges may make its branch vertices of a graph subdivision have larger degrees of vertices than their target counterparts.

This distinction matters when a network's individual junctions have a limited number of connections: replacing a connection by a route preserves the number of routes meeting at each chosen junction, while contracting a connected region can combine connections from separate junctions. It also explains why a small nonplanar pattern can hide inside long routes. By Kuratowski's theorem, a finite simple graph is a planar graph exactly when it has neither the complete graph $K_5$ nor the complete bipartite graph $K_{3,3}$ as a topological minor. The obstruction is a graph subdivision inside the network, regardless of the number of intermediate vertices.