Structure of Plane Graphs

Author: Joseph Malkevitch

An especially interesting collection of dots and lines diagrams, known as graphs, are those which consist of dots which can be or have been drawn in the Euclidean plane with four line segments meeting at every vertex (dot).

These graphs can be referred to as 4-valent or having every vertex of degree 4 (the degree of a vertex is the number of edges which meet at the vertex). If the drawing has the property that edges (lines) of the graph only meet at vertices and the graph consists of one piece (connected) the graph is known as a degree 4 (4-valent) connected plane graph.

Depending on the "rules" for what constitutes a graph, it is possible for the graph to have regions (faces) which have one side (1-gon) or two sides (digons). Figure 1 shows a 4-valent plane graph with 10 vertices. For the most part I will be dealing with connected 4-valent plane graphs which have regions with at least three sides but many of the issues raised can be investigated for more general 4-valent graphs. Henceforth I will refer only to plane connected 4-valent graphs. Note, however, that graphs that are drawn in the plane may have crossings where edges meet at points which are not vertices.

Note: The information below was created with the assistance of AI.

Category	Summary
Recommended Mathematics Level	Advanced High School / Introductory College (approximately Grades 10–12+). The basic ideas—vertices, edges, paths, circuits, counting, and Euler’s formula—are accessible to strong secondary students, while 3-connected graphs, 3-polytopal graphs, medial graphs, and open-ended research investigations move toward undergraduate discrete mathematics.
Primary Application Areas	Graph Theory and Discrete Mathematics; Combinatorics; Discrete Geometry; Operations Research; Network Modeling; Polyhedral Geometry. The article explicitly connects Eulerian circuits to service-routing applications such as snow plowing and garbage collection.
Prerequisites	Students should be comfortable with basic algebra, arithmetic, geometric figures and polygons, coordinate/plane reasoning, patterns, logical reasoning, and elementary counting. No calculus is required. Previous exposure to graphs/networks is useful but not necessary because important terminology is introduced in the article.
Major Subject Matter	Plane and planar graphs; vertices, edges, faces and degree/valence; connected graphs; 4-valent graphs; Eulerian circuits; cut-through Eulerian (CTE) circuits; simple circuits/cycles; Euler’s Polyhedral Formula; 3-connected graphs; convex polyhedra; regular octahedra and antiprisms; graph transformations; medial graphs; Venn diagrams; and mathematical investigation/conjecture. The central objects are connected plane graphs in which every vertex has degree 4.
Key Mathematical Relationships	Students count vertices $VV$ , edges $EE$ , and faces $FF$ and use Euler’s Polyhedral Formula $V+F-E =2 V + F - E =2$ . For 4-valent plane graphs, the article develops relationships between vertex degrees, edges, and the numbers $p(i)p(i)$ of faces having $ii$ sides.
Mathematical Practices / Problem Solving	The article emphasizes constructing examples, looking for patterns, forming conjectures, testing cases, analyzing invariants, generalizing transformations, and communicating mathematical arguments. Students are asked to determine which graphs can exist under particular conditions and to track how properties change when graphs are transformed.
Research/Extension Level	Particularly appropriate for mathematical modeling clubs, enrichment courses, independent research, contests, or undergraduate introductory discrete mathematics. The concluding investigations ask students to construct new graphs while tracking $V,F,E,p (i) V,F,E,p (i)$ , circuit structure, connectivity, and Eulerian properties.

Correlation to Mathematics Standards

The article does not explicitly identify a standards framework, so the following is an instructional alignment rather than a stated correlation in the source.

Common Core State Standards – Mathematical Practice: Strong alignment with MP1 Make sense of problems and persevere in solving them; MP2 Reason abstractly and quantitatively; MP3 Construct viable arguments and critique reasoning; MP4 Model with mathematics; MP7 Look for and make use of structure; and MP8 Look for and express regularity in repeated reasoning.

High School Geometry: Partial alignment with geometric reasoning concerning two- and three-dimensional figures, polygons, plane representations, and relationships between planar graphs and convex polyhedra. The article specifically studies when planar, 3-connected graphs correspond to the edge-vertex graphs of three-dimensional convex polyhedra.

Overall Assessment

Structure of Plane Graphs is best classified as an advanced secondary-school enrichment / introductory college discrete mathematics investigation. Its strength is that relatively elementary counting and geometry lead naturally into authentic graph-theoretic research. Students move beyond routine calculation to constructing, analyzing, conjecturing, proving, and generalizing, making the material especially suitable for a Student Research Corner, mathematics modeling/enrichment program, or advanced high-school discrete mathematics unit.