OctoInformBeta

OpenAI preprint, September 2026 · Section 1. Introduction

§1 (setting): planarity, connectivity, and a Hamiltonian cycle: Planarity and three-vertex-connectivity in simple graphs

Plane embeddings and Hamiltonian cycles.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Let G=(V,E)G=(V,E) be a simple graph, with adjacency written v∼wv\sim w. For a set S⊆VS\subseteq V, write G−SG-S for the subgraph induced by V\SV\setminus S.

The Definition

Definition 1. A plane embedding (φ,γ)(\varphi,\gamma) of GG is a placement of its vertices in ℝ2\mathbb R^2 together with continuous edge arcs satisfying (1).✦ Each arc γvw\gamma_{vw} is indexed by an ordered adjacent pair v,wv,w; a hooked arrow denotes an injective map. φ:V↪ℝ2,γvw:[0,1]↪ℝ2(v∼w),γvw is continuous,γvw(0)=φ(v),γvw(1)=φ(w)(v∼w),γwv(t)=γvw(1−t)(v∼w,t∈[0,1]),γvw((0,1))∩φ(V)=⌀(v∼w),γvw((0,1))∩γxy((0,1))=⌀(v∼w,x∼y,{v,w}≠{x,y}).\begin{aligned} &\varphi:V\hookrightarrow\mathbb R^2, \qquad \gamma_{vw}:[0,1]\hookrightarrow\mathbb R^2 && (v\sim w),\\ &\gamma_{vw}\text{ is continuous},\qquad \gamma_{vw}(0)=\varphi(v),\quad \gamma_{vw}(1)=\varphi(w) && (v\sim w),\\ &\gamma_{wv}(t)=\gamma_{vw}(1-t) && (v\sim w,\ t\in[0,1]),\\ &\gamma_{vw}((0,1))\cap\varphi(V)=\varnothing && (v\sim w),\\ &\gamma_{vw}((0,1))\cap\gamma_{xy}((0,1))=\varnothing && \left(\substack{v\sim w,\ x\sim y,\\ \{v,w\}\ne\{x,y\}}\right). \end{aligned}(1)✦

A planar graph GG is a graph admitting a plane embedding, as in (2).✦ G is planar⇔there exists a plane embedding of G.\text{$G$ is planar} \quad\Longleftrightarrow\quad \text{there exists a plane embedding of $G$}.(2)✦

A three-vertex-connected graph GG is a finite graph with at least four vertices that remains connected after deleting any set of at most two vertices, as in (3).✦ |V|≥4,G−S is connected(S⊆V,|S|≤2).\begin{aligned} |V|&\geq 4,\\ G-S&\text{ is connected}\qquad(S\subseteq V,\ |S|\leq 2). \end{aligned}(3)✦

A Hamiltonian graph GG is a graph containing a cycle through every vertex, as in (4).✦ For a walk pp, let V(p)V(p) be the set of vertices it visits, and let p:v⤳Gvp:v\leadsto_G v denote a closed walk based at vv. G is Hamiltonian⇔∃v∈V∃p:v⤳Gv,p is a cycle and V(p)=V.\begin{gathered} \text{$G$ is Hamiltonian}\quad\Longleftrightarrow\\ \exists\,v\in V\ \exists\,p:v\leadsto_G v, \qquad p\text{ is a cycle and }V(p)=V. \end{gathered}(4)✦

What Is Checked

The definitions (1), (2), and (4) are stated for simple graphs, with edge arcs in the real plane for (1); the definition (3) is stated for finite simple graphs.