VectorPaint complete three-by-three bipartite graphs: crossings are not vertices and nonplanarity needs proof

English translation of the Chinese original, translated on 2026-11-14. Original publication dates, attribution, code and version notes are retained.

Connecting three sources to all three destinations produces complete bipartite graph K3,3. Audit nine connections and crossing notation in VectorPaint, then verify a nonplanarity argument externally. One failed attempt at a crossing-free drawing is not proof, and no automatic planarity detection is implied.

Declare the two parts and required connections

Name left nodes A,B,C and right nodes 1,2,3. List A1,A2,A3,B1,B2,B3,C1,C2,C3 before drawing. Edges cross between parts only; AB,12 and self-loops are excluded. Use a 1600×1200 canvas with vertical spacing 300 and horizontal spacing 800, leaving room for crossing explanations. Distinguish groups by shapes and names, with colour supplementary so grayscale still reveals both three-node parts.

Draw edges against the nine-pair ledger

Draw three edges from A, then three each from B and C, checking off every pair externally. Straight or gently curved paths have the same endpoint relation. Do not dot crossings as vertices. A bridge-shaped crossover is only nonconnection notation, not an actual elevation into 3D. Position edge identifiers where both ends can be traced and keep right-node numbers distinct from edge numbering. Each node has degree three; degree sum eighteen divided by two gives nine edges.

Separate a crossed drawing from a nonplanar graph

Crossings in this straight layout establish only that this layout is crossed, not that every layout must be. The authors’ combinatorics textbook on planar graphs distinguishes a crossing-free embedding from a particular drawing. Separate observed crossings from the proposition that no crossing-free planar drawing exists. Curving edges may reduce crossings, but recheck all nine pairs; deleting a difficult edge does not solve the original problem.

Calculate faces under a crossing-free assumption

Assume for contradiction that this connected six-vertex, nine-edge graph has a crossing-free plane embedding. Euler’s V−E+F=2 then gives five faces, including the unbounded exterior. These five arise under the assumption; they are not counted from the current crossed drawing. Nonvertex crossings cannot partition a drawing into regions to which the same six/nine data are blindly applied. Write the assumption above the formula so five faces are not mistaken for a successfully constructed plane embedding.

Use bipartition to require at least four boundary edges

Every step switches parts, so an odd-length cycle cannot return to its starting part; triangles are impossible. K3,3 is simple, without loops or parallel edges, and every edge lies in a four-cycle rather than being a bridge. Under the assumed plane embedding, every face therefore has at least four boundary-edge appearances. Trace A→1→B→2→A as an alternating four-cycle. Retain “at least four”, not a claim that every bipartite face has exactly four. Longer faces are permitted; the lower bound is sufficient.

Double-count incidences to obtain eighteen versus twenty

Five faces require at least twenty boundary incidences. Counting the two sides of each of nine edges gives exactly eighteen, an impossible eighteen-at-least-twenty inequality. Reject the crossing-free assumption. Keep face lower bound and exact edge count separate; twenty is not a count of newly created edges. The Euler relation and bipartite corollary supply general context; independently calculate this example’s 6,9,5 and 18,20. The proof concerns the specified nine-edge graph, not all six-vertex graphs. Removing one edge gives eight edges, four assumed faces and sixteen incidences without contradiction. This count no longer rules it out; absence of contradiction alone does not construct a planar drawing.

Troubleshoot crossover notation mistaken for a solution

A bridge symbol indicates nonconnection but does not eliminate a planar crossing. Real overpasses, layered pipes or routing on a torus change the problem’s conditions and do not refute the plane result. Adding a shared vertex at a crossing changes vertex count and adjacency, requiring a new ledger. Check for duplicated pairs and missing C3: nine path objects alone cannot replace an endpoint audit. The application has not proved nonplanarity; the proof is the external conditional argument, while the canvas displays relations and explanations.

Reopen and audit nine pairs and the assumption chain

Save, leave and reopen. Trace three edges per node and all nine pairs, retaining exactly six vertices and nonconnecting crossings. Hide the conclusion and reconstruct 6−9+F=2, F=5 and 4F≤2E, yielding impossible 20≤18. Delivery must retain the exterior-face note, at-least-four conditions and crossover legend rather than just a nonplanar slogan. Leave unexamined formats unverified. Both adjacency and proof should be independently recoverable, instead of turning one dragging experience into an impossibility theorem.