Fact-checked by Grok 2 weeks ago

Cubic graph

In graph theory, a cubic graph is a connected graph in which every vertex has degree exactly three, also known as a 3-regular or trivalent graph.^[1] Such graphs must have an even number of vertices, since the sum of all vertex degrees is twice the number of edges and thus even, implying that 3 times the number of vertices is even.^[2] The number of edges in a cubic graph with n vertices is therefore 3n/2.^[1] Cubic graphs have played a central role in the development of graph theory since the late 19th century, with early studies by P. G. Tait in 1878–1880 linking them to the four-color problem for planar maps, and by Julius Petersen in 1891 introducing the famous Petersen graph as a counterexample to various conjectures.^[1] The Petersen graph, a non-planar cubic graph on 10 vertices, is notable for being 3-connected, having girth 5, and lacking a Hamiltonian cycle, making it a key example in structural graph theory.^[2] Other prominent cubic graphs include the complete bipartite graph K_{3,3} (the smallest non-planar cubic graph and one of the two minimal forbidden minors for planarity in Kuratowski's theorem) and Tutte's graph (a counterexample to Tait's conjecture that every 3-connected planar cubic graph is Hamiltonian).^[1] Beyond historical significance, cubic graphs are important in complexity theory, as problems like determining the existence of a Hamiltonian cycle remain NP-complete even when restricted to cubic graphs.^[3] They also model real-world structures, such as chemical compounds in organic chemistry and interconnection networks in parallel computing, due to their sparsity and regularity.^[4] Research on cubic graphs continues to explore properties like edge-coloring (always possible with four colors by Vizing's theorem for cubic graphs) and snarks (cubic graphs that are non-3-edge-colorable, relevant to the four-color theorem).^[1]

Definition and Fundamentals

Definition

A cubic graph is a connected simple undirected graph in which every vertex has degree exactly three.^[5] It is also referred to as a 3-regular graph or a trivalent graph.^[5] This terminology specifically applies to simple graphs without loops or multiple edges between the same pair of vertices; extensions to multigraphs or directed graphs exist but are distinguished by additional qualifiers, such as cubic multigraphs allowing parallel edges.^[6] By the handshaking lemma, the sum of all vertex degrees equals twice the number of edges, yielding $3n = 2e where n is the number of vertices and e is the number of edges, so e = \frac{3n}{2}.^[5] Consequently, n must be even and at least 4, as smaller even values like n=2 cannot form a simple graph with degree 3 at each vertex.^[5] The handshaking lemma was established by Leonhard Euler in 1736.^[7] The term "cubic" derives from the Latin cubus for cube, referring to the analogy with the cube, a polyhedron where each vertex has degree three.^[5]

Basic Characteristics

A cubic graph must have an even number of vertices, as the handshaking lemma implies that the sum of degrees, which is $3n for n vertices, must be even.^[8] The smallest such graph has 4 vertices and is the complete graph K_4.^[5] The number of edges in a cubic graph with n vertices is exactly e = \frac{3n}{2}, following directly from the handshaking lemma.^[8] The adjacency matrix A of a cubic graph has each row and column summing to 3, reflecting the uniform degree.^[9] The largest eigenvalue of A is 3, with the all-ones vector as the corresponding eigenvector.^[10] Unlike 2-regular graphs, which consist of disjoint cycles, cubic graphs exhibit greater interconnectivity due to the higher degree.^[11] In contrast, 4-regular graphs have twice as many edges relative to vertices, allowing for denser structures without delving into specific connectivity details. A bicubic graph is a cubic graph that is also bipartite, necessitating equal-sized partitions of \frac{n}{2} vertices each to balance the degrees across the bipartition.^[12]^[13]

Examples and Constructions

Small Cubic Graphs

The smallest cubic graph is the complete graph K_4, also known as the tetrahedral graph, which has 4 vertices and is the unique such graph up to isomorphism. This graph is 3-connected and serves as a foundational example of a cubic graph, where every vertex connects to all others. For 6 vertices, there are two non-isomorphic connected cubic graphs. One is the complete bipartite graph K_{3,3}, called the utility graph, which is bipartite, 3-connected, and famously non-planar as demonstrated by its role in Kuratowski's theorem. The other is the triangular prism graph, formed by two disjoint triangles connected by matching edges, which is planar and vertex-transitive. With 8 vertices, there are five non-isomorphic connected cubic graphs. Notable among them is the cube graph, or 3-dimensional hypercube Q_3, a bipartite 3-regular graph that models the vertices and edges of a cube and is Hamiltonian. Another prominent example is the Möbius ladder on 8 vertices, also known as the Wagner graph, which is a 3-regular circulant graph with girth 4 and is embeddable on a Möbius strip. These, along with the other three, illustrate varying levels of symmetry and planarity in small cubic structures. The case of 10 vertices yields 19 non-isomorphic connected cubic graphs. The most renowned is the Petersen graph, a 3-regular graph with girth 5 that serves as the unique (3,5)-cage graph and is a key example in graph theory for its non-Hamiltonian nature and high symmetry. Among the symmetric cubic graphs in these small orders, the Foster census provides a comprehensive catalog, beginning with K_4, K_{3,3}, Q_3, the Wagner graph, and the Petersen graph as the vertex-transitive entries up to 10 vertices. These enumerations, originally compiled by de Vries and later refined computationally, highlight the rapid growth in the diversity of cubic graphs even at small scales.

Notable and Infinite Families

The Heawood graph is a prominent cubic graph with 14 vertices and 21 edges, recognized as the point-line incidence graph of the Fano plane, a projective plane of order 2, and as the unique (3,6)-cage graph, meaning the smallest 3-regular graph with girth 6.^[14] The Tutte graph, constructed by W. T. Tutte in 1946, is a 3-connected planar cubic graph on 46 vertices that serves as a counterexample to Tait's conjecture, demonstrating that not all such graphs are Hamiltonian.^[15] Another significant example is the Gray graph, discovered in 1932 and first published in 1968, which is the smallest semi-symmetric cubic graph with 54 vertices and 81 edges, exhibiting vertex-transitivity but not edge-transitivity.^[16] Infinite families of cubic graphs provide systematic constructions with recurring structural features. Prism graphs, formed as the Cartesian product of an even cycle C_n (for n \geq 4) and the complete graph K_2, yield an infinite sequence of bipartite 3-regular Hamiltonian graphs.^[17] Möbius ladders, denoted M_n for n \geq 3, generalize the prism construction by introducing a cross-rung twist, resulting in non-bipartite cubic graphs on $2n vertices that are hypohamiltonian for certain n.^[18] The generalized Petersen graphs G(n,k), defined for integers n > 2k \geq 1 with \gcd(n,k)=1, form a broad infinite family of cubic graphs featuring an outer n-cycle, an inner star-like structure, and connecting spokes, many of which display high symmetry and are used in cage problem studies.^[19] Snarks constitute a key infinite family of cyclically 4-edge-connected cubic graphs that are non-3-edge-colorable, playing a central role in counterexamples to the four-color theorem via Tait coloring equivalences. Notable subfamilies include the flower snarks J_n for odd n \geq 5, constructed by encircling odd cycles with alternating spoke connections, and the Blanuša snarks, which extend the Petersen graph through specific edge insertions to generate larger non-Hamiltonian examples.^[20] Bipartite cubic graphs, or bicubic graphs, admit infinite families such as the incidence graphs of finite projective planes of order 2 (yielding the Heawood graph) and higher analogs in generalized geometries, alongside constructions like balanced incomplete block designs with replication number 3, ensuring equal partition sizes and 3-regularity on both sides.^[14] Constructions of cubic graphs frequently leverage transformations and algebraic methods for generating families with desired properties. The YΔY transformation, involving the replacement of a degree-3 vertex (Y) with a triangle (Δ) or vice versa, preserves cubic regularity and is used to reduce or build planar cubic graphs while maintaining properties like 3-edge-connectivity.^[21] Voltage graph techniques, based on group homomorphisms assigning voltages to edges of a base graph, enable the derivation of regular covering graphs, including infinite families of cubic Cayley graphs on finite groups like the alternating group A_4 or dihedral groups, which are vertex-transitive by construction.^[22]

Structural Properties

Connectivity

In connected cubic graphs, the vertex connectivity equals the edge connectivity. This follows from the general bounds κ(G) ≤ λ(G) ≤ δ(G) = 3 and the fact that a vertex cut of size 1 or 2 in a cubic graph implies a corresponding edge cut of the same size. Bridges, or 1-edge-cuts, can occur in connected cubic graphs but are rare and limited to specific constructions where each component after removal has an odd number of vertices to satisfy the handshaking lemma. For instance, one such graph can be formed by taking two simple graphs, each with 5 vertices where four vertices have degree 3 and one has degree 2 (e.g., a 5-cycle with two non-incident chords), and connecting the degree-2 vertices with a single edge to yield a 10-vertex connected cubic graph with a bridge. However, bridges violate the even parity of odd-degree vertices in components unless the orders are odd, making such graphs atypical compared to the bridgeless ones central to much of graph theory research on cubic graphs. A cubic graph is bridgeless if and only if its edge connectivity is at least 2. By Whitney's theorem, this is equivalent to the graph being 2-vertex-connected. For bridgeless cubic graphs, the connectivity (both vertex and edge) is therefore 2 or 3, with minimum cuts of size 2 separating the graph into two components or size 3 providing the smallest separating sets in more robust cases. Cubic graphs with connectivity 2 exhibit 2-edge-cuts (and thus 2-vertex-cuts), representing minimally connected examples beyond trees, which cannot be cubic due to degree constraints but can inspire constructions like adding edges to tree-like structures while maintaining regularity. Representative examples include certain planar cubic Cayley graphs, such as those classified as having connectivity exactly 2. In contrast, bridgeless cubic graphs with no 2-edge-cuts are 3-edge-connected and, by the equality of connectivities, 3-vertex-connected; an adaptation of Menger's theorem ensures at least three vertex-disjoint paths between any pair of vertices in such graphs, given the minimum degree of 3.

Matchings

In cubic graphs, which are 3-regular and thus have an even number of vertices, a perfect matching—also known as a 1-factor—is a set of edges without common vertices that covers every vertex exactly once. The existence of such matchings is a central topic in the structural theory of these graphs. A foundational result is Petersen's theorem, which states that every bridgeless cubic graph contains at least one perfect matching. This theorem, proved in 1891, guarantees the presence of a 1-factor in any cubic graph without bridges, providing a key tool for understanding edge covers and decompositions in such graphs.^[23] Petersen's theorem is a special case of the more general Tutte's theorem from 1947, which characterizes graphs with perfect matchings via the condition that for every vertex subset S, the number of odd components in the graph induced by V \setminus S is at most |S|. In the context of cubic graphs, this condition simplifies due to the regularity: a bridgeless cubic graph satisfies Tutte's criterion because any potential obstructing set S (a Tutte set) would induce bridges, contradicting bridgelessness. For example, the complete graph K_4, a cubic graph on 4 vertices, admits exactly three perfect matchings, each consisting of two disjoint edges, and these can collectively decompose all six edges of the graph. In contrast, the Petersen graph, a bridgeless cubic graph on 10 vertices, has exactly six perfect matchings but lacks a decomposition into three disjoint ones covering all edges. While every bridgeless cubic graph has a perfect matching, a 1-factorization—decomposing the edge set into three disjoint perfect matchings—is not always possible, as evidenced by the Petersen graph, which requires more than three to cover its edges. This limitation ties into broader conjectures on edge covers; notably, Fulkerson's conjecture states that every 2-connected cubic graph admits a double cover by six perfect matchings, where each edge lies in exactly two of them. This would mean the edge set is covered twice over by these matchings, strengthening Petersen's result but remaining unproven.^[24]

Symmetry

Vertex-Transitivity

A cubic graph is vertex-transitive if its automorphism group acts transitively on the set of vertices, meaning that for any pair of vertices, there exists an automorphism of the graph that maps one to the other. This property ensures that all vertices are structurally equivalent, sharing the same local neighborhood up to isomorphism. Vertex-transitivity implies that the graph is regular, as every vertex must have the same degree; however, the converse does not hold, since there exist 3-regular graphs whose automorphism groups do not act transitively on vertices.^[25]^[26] Prominent examples of vertex-transitive cubic graphs include the complete graph K_4 on 4 vertices, the graph of the 3-dimensional cube (or 3-cube) on 8 vertices, and the Petersen graph on 10 vertices, all of which exhibit full symmetry under their automorphism groups. These graphs demonstrate high degrees of regularity and symmetry, with the Petersen graph serving as a canonical non-Hamiltonian example despite its transitivity properties.^[27] Cayley graphs provide a systematic construction of vertex-transitive cubic graphs. Specifically, a cubic Cayley graph arises as the Cayley graph \mathrm{Cay}(G, S) of a group G with respect to a generating set S of three elements such that S = S^{-1} and the identity is excluded from S; the left regular action of G on itself ensures vertex-transitivity. Such graphs are particularly useful for studying group-theoretic properties in graph symmetry.^[28] Enumerations of vertex-transitive cubic graphs have been compiled using computational methods. For instance, the Online Encyclopedia of Integer Sequences records 76 connected cubic vertex-transitive graphs on at most 32 vertices, distributed across even orders from 4 to 32. The Foster census, originally compiled by Ronald M. Foster, catalogs cubic symmetric graphs (a subclass that is both vertex- and edge-transitive) up to 512 vertices, with extensions to larger orders facilitating further study.^[29]^[30]

Arc-Transitivity

In graph theory, an arc of an undirected graph is an ordered pair of adjacent vertices, representing a directed edge. A connected graph is s-arc-transitive, for integer s ≥ 1, if its automorphism group acts transitively on the set of all s-arcs, where an s-arc is a sequence of s+1 vertices in which consecutive vertices are adjacent and no repetition occurs until the end. For s = 1, s-arc-transitivity is equivalent to arc-transitivity, meaning the graph is both vertex-transitive and edge-transitive. In the case of cubic graphs, which are 3-regular, arc-transitivity ensures a high degree of symmetry, as the automorphism group must map any directed edge to any other while preserving the structure.^[31]^[32] For cubic graphs, higher levels of arc-transitivity imply even stronger symmetry. Specifically, a cubic graph that is 3-arc-transitive is fully symmetric, meaning its automorphism group acts transitively not only on vertices and arcs but also on the incident triples of a vertex (i.e., flags consisting of a vertex and two adjacent edges). This full symmetry distinguishes such graphs from those that are merely 1- or 2-arc-transitive. In 1947, W. T. Tutte provided a complete classification of finite connected cubic s-arc-transitive graphs for s ≤ 5, demonstrating that only finitely many exist for each s in this range and none for s > 5. Tutte's analysis showed that the possible automorphism groups are limited, and that infinite families of such graphs exist for s ≤ 5. This result underscores the bound on the level of arc-transitivity in cubic graphs.^[33]^[34] Prominent examples of arc-transitive cubic graphs include the Heawood graph on 14 vertices, which is 3-arc-transitive and serves as the unique (3,6)-cage graph, embedding on the torus with girth 6. The McGee graph on 24 vertices is another arc-transitive cubic graph, known as the unique (3,7)-cage with girth 7. In contrast, semi-symmetric cubic graphs are vertex-transitive but not arc-transitive (hence not edge-transitive), providing examples where symmetry is partial; the Gray graph on 54 vertices is the smallest such cubic semi-symmetric graph. The Foster census, initiated by Ronald M. Foster in 1932, systematically catalogs all known finite connected arc-transitive cubic graphs, with the list now complete up to 768 vertices, comprising 85 such graphs on at most 512 vertices.^[35]^[36]^[37]^[38] A notable example of even higher symmetry is the Biggs-Smith graph on 102 vertices, which is cubic, arc-transitive, distance-regular, and distance-transitive—the largest known finite cubic distance-transitive graph. Distance-transitivity means the automorphism group acts transitively on pairs of vertices at any fixed distance, implying arc-transitivity as a consequence. This graph highlights the intersection of arc-transitivity with broader symmetry properties in cubic structures.^[39]^[40]

Coloring Properties

Vertex Coloring

A proper vertex coloring of a cubic graph assigns colors to its vertices such that no two adjacent vertices share the same color, with the chromatic number \chi(G) denoting the minimum number of colors required. For connected cubic graphs, Brooks' theorem establishes that \chi(G) \leq 3, except for the complete graph K_4, which requires 4 colors. This bound holds because cubic graphs have maximum degree \Delta(G) = 3, and the theorem applies to connected graphs that are neither complete graphs K_{\Delta+1} nor odd cycles (the latter being 2-regular and thus inapplicable to cubic graphs). The proof of Brooks' theorem for cubic graphs proceeds by contradiction: assume \chi(G) = 4; then G must be 3-regular and critical (removing any vertex reduces the chromatic number), leading to a structure isomorphic to K_4. A simpler greedy coloring argument also suffices: order the vertices and color each with the smallest available color not used by its at most three neighbors, ensuring at most four colors, but the exception analysis tightens this to three except for K_4. Bipartite cubic graphs achieve \chi(G) = 2, as all bipartite graphs are 2-colorable. In contrast, non-bipartite cubic graphs contain odd cycles and thus require at least 3 colors. The Petersen graph exemplifies a non-bipartite cubic graph with \chi(G) = 3, despite being triangle-free.^[41] Grötzsch's theorem, which guarantees 3-colorability for triangle-free planar graphs, does not directly apply to all triangle-free cubic graphs, as such graphs need not be planar (e.g., the Petersen graph embeds on a torus).

Edge Coloring

In graph theory, the edge chromatic number \chi'(G) of a simple cubic graph G, which has maximum degree \Delta(G) = 3, is either 3 or 4 by Vizing's theorem.^[42] This classification divides cubic graphs into two types: class 1 graphs, which admit a proper 3-edge-coloring (also known as a Tait coloring), and class 2 graphs, which require 4 colors.^[43] A Tait coloring partitions the edges into three perfect matchings, ensuring no two adjacent edges share the same color.^[43] Class 2 cubic graphs include snarks, which are cyclically 4-edge-connected cubic graphs with \chi'(G) = 4.^[44] The Petersen graph is the smallest snark, with 10 vertices and \chi'(G) = 4.^[41] In contrast, the complete graph K_4 is a class 1 cubic graph, as its 6 edges can be properly colored with 3 colors via a 1-factorization. Determining whether a cubic graph is class 1 or class 2 is NP-complete, as proven by Holyer, who showed that deciding the edge chromatic number for cubic graphs is computationally intractable.^[45] Infinite families of snarks, such as the flower snarks introduced by Isaacs, provide examples of class 2 cubic graphs that are cyclically 4-edge-connected and require 4 colors.^[46]

Independence and Coverings

Independent Sets

In cubic graphs, the independence number \alpha(G), which is the size of a maximum independent set, satisfies \alpha(G) \leq n/2, where n is the number of vertices; this bound is tight for bipartite cubic graphs, such as the utility graph K_{3,3}, where the larger part forms an independent set of size n/2. For connected cubic graphs other than the complete graph K_4, Brooks' theorem implies that the chromatic number \chi(G) \leq 3, and thus \alpha(G) \geq n/\chi(G) \geq n/3. This bound improves upon the general Caro-Wei lower bound of \alpha(G) \geq n/4 for 3-regular graphs and is asymptotically tight for certain snarks and other 3-chromatic cubic graphs.^[47] In triangle-free cubic graphs, a stronger lower bound holds: \alpha(G) \geq 5n/14. This result, originally due to Staton and provided with a simpler proof by Heckman and Thomas, is best possible, as equality is achieved by the generalized Petersen graph GP(7,2) on 14 vertices.^[48] Representative examples illustrate these bounds. The Petersen graph, a famous non-Hamiltonian cubic graph with 10 vertices, has \alpha(G) = 4 > 10/3.^[41] In contrast, bipartite cubic graphs attain the upper bound \alpha(G) = n/2. While maximum independent sets in cubic graphs often serve as efficient dominating sets—providing a lower bound on the domination number—the primary structural insight lies in their size bounds, which inform stability and covering properties without relying on complements or algorithmic details.

Vertex Cover

A vertex cover of a cubic graph G = (V, E) with n = |V| vertices is a subset C \subseteq V such that every edge in E is incident to at least one vertex in C. The minimum vertex cover problem seeks a vertex cover of minimum cardinality, denoted \tau(G).^[49] By Gallai's theorem, the size of a minimum vertex cover equals the number of vertices minus the size of a maximum independent set, \tau(G) = n - \alpha(G). This identity establishes a direct complementarily between minimum vertex covers and maximum independent sets; specifically, the complement of any maximum independent set is a minimum vertex cover, and vice versa. As detailed in the section on independent sets, the independence number \alpha(G) for cubic graphs satisfies \alpha(G) \leq n/2, implying \tau(G) \geq n/2. The lower bound \tau(G) \geq n/2 also follows from the edge count in a cubic graph, which has exactly $3n/2 edges, with each vertex in a cover incident to at most 3 edges.^[50] This bound is tight, as it is achieved in bipartite cubic graphs with perfect matchings. In particular, for bipartite graphs, König's theorem states that \tau(G) = \nu(G), where \nu(G) is the size of a maximum matching; thus, in a bipartite cubic graph with a perfect matching, \nu(G) = n/2 and \tau(G) = n/2. The minimum vertex cover problem remains NP-hard even when restricted to cubic graphs and is APX-hard, meaning there is no polynomial-time approximation scheme unless P = NP. A simple 2-approximation algorithm for general graphs, which selects both endpoints of edges in a maximum matching, applies directly to cubic graphs and guarantees a vertex cover of size at most $2\tau(G). Better constant-factor approximations exist for low-degree graphs like cubic ones, though the optimal ratio remains an open question beyond the known hardness thresholds. Representative examples illustrate these properties. The complete graph K_4, a cubic graph on 4 vertices, has \tau(K_4) = 3, as removing any 3 vertices leaves at most one isolated vertex with no edges uncovered. The Petersen graph on 10 vertices has independence number \alpha = 4, so \tau = 6 by Gallai's theorem; a minimum vertex cover consists of 6 vertices that cover all 15 edges.^[41] In the utility graph K_{3,3}, a bipartite cubic graph on 6 vertices, \tau(K_{3,3}) = 3 = n/2, matching its maximum matching size. Gallai's identities extend beyond the basic relation, providing additional structural insights applicable to cubic graphs without isolated vertices. For instance, the edge cover number \rho(G) satisfies \rho(G) = n - \nu(G), and combined with the vertex cover identity, these relate coverings and packings in regular graphs of degree 3. However, specific computations for \tau(G) in cubic graphs often rely on the independence number or matching properties due to the graph's regularity.

Topological Properties

Embeddings

In graph theory, an embedding of a cubic graph refers to a representation of the graph on a surface such that edges intersect only at vertices, with the genus denoting the minimum genus of an orientable surface allowing such a crossing-free embedding. For cubic graphs, determining the genus is computationally challenging, as the problem of deciding whether a given cubic graph embeds on a surface of specified genus is NP-complete.^[51] The genus provides insight into the topological complexity of cubic graphs, with planar cubic graphs having genus 0 and non-planar ones requiring higher genera. A prominent example of a cubic graph with genus 1 is the complete bipartite graph K_{3,3}, which is non-planar but embeds without crossings on the torus. Similarly, the Petersen graph, a well-known non-planar cubic graph on 10 vertices, also has genus 1 and admits a toroidal embedding.^[52] The Heawood graph, a cubic graph on 14 vertices, represents the minimal such example for genus 1; it embeds on the torus as the dual of the complete graph K_7, forming seven mutually adjacent hexagonal faces that demonstrate the tightness of the seven-color theorem for toroidal maps.^[53] The Ringel-Youngs theorem, resolving the Heawood conjecture on map coloring, has significant applications to embeddings of cubic graphs through their role as duals of triangular maps on surfaces. The theorem constructs embeddings of complete graphs K_n on orientable surfaces of genus \lceil \frac{(n-3)(n-4)}{12} \rceil, and the dual graphs of these embeddings are cubic graphs that achieve the bound for the chromatic number of the surface, providing canonical examples of cubic embeddings for higher genera.^[54] Voltage graphs offer a systematic method for constructing embeddings of cubic graphs, particularly symmetric ones, by assigning voltages from a group to arcs of a base graph to derive covering spaces and their surface realizations. This approach yields canonical embeddings, where the rotation systems and face structures are derived uniformly from the voltage assignments, facilitating the study of cubic graphs with prescribed automorphism groups on surfaces.^[55] Embeddings of cubic graphs also underpin map colorings, as the faces of a cubic embedding form a map whose regions correspond to the dual graph's vertices, allowing the chromatic number of the surface to be analyzed through the graph's embedding properties without delving into edge or vertex colorings of the primal graph itself.^[56]

Planarity and Genus

A 3-connected cubic planar graph admits a unique embedding in the plane up to homeomorphism and reflection of the plane. This follows from Whitney's theorem on the uniqueness of embeddings for 3-connected planar graphs, which applies directly to the cubic case since such graphs are polyhedral by Steinitz's theorem. For a connected planar cubic graph with v vertices, Euler's formula v - e + f = 2 holds, where e = 3v/2 is the number of edges and f is the number of faces (including the outer face).^[57] Substituting yields f = v/2 + 2. Additionally, since each face has at least three edges and each edge bounds two faces, $2e \geq 3f, so f \leq 2e/3 = v; the Euler-derived value satisfies this inequality for v \geq 4.^[57] Not all cubic graphs are planar. The complete bipartite graph K_{3,3} is a cubic graph with 6 vertices that is non-planar, as it is one of the forbidden minors in Kuratowski's theorem. Similarly, the Petersen graph, a cubic graph with 10 vertices, is non-planar because it contains a subdivision of K_{3,3}. Both K_{3,3} and the Petersen graph have orientable genus 1, meaning they embed without crossings on the torus but not on the sphere.^[58]^[59] The minimal orientable genus \gamma(G) of a simple graph G satisfies the lower bound \gamma(G) \geq \lceil (e - 3v + 6)/6 \rceil, derived from Euler's characteristic assuming a maximal number of faces with degree at least 3. For simple cubic graphs, e = 3v/2, so this simplifies to \gamma(G) \geq \lceil (-3v/2 + 6)/6 \rceil = \lceil -v/4 + 1 \rceil, which equals 0 for v \geq 8 (taking \max\{0, \lceil \cdot \rceil\} since genus \geq 0). This bound is consistent with planarity possibilities for small v but provides no lower bound greater than 0 for non-planar examples like the Petersen graph, whose actual genus is 1. This bound arises from estimating the deficiency relative to the planar case e \leq 3v - 6. Barnette's conjecture, posed in 1969, states that every 3-connected planar cubic bipartite graph is Hamiltonian; this remains open as of 2025 despite verification for all such graphs up to 90 vertices (as of 2021).^[60]^[61] The conjecture has implications for decompositions and matchings in such graphs.^[62] In the theory of maps on surfaces, a cubic graph embedding can be thickened to a 4-regular map by constructing its medial graph, where vertices correspond to midpoints of the original edges and edges connect adjacent midpoints around faces; this 4-regular structure aids in analyzing colorings and flows on the surface.^[63]

Geometric Aspects

Polyhedral Graphs

A polyhedral cubic graph is the 1-skeleton of a convex polyhedron in which every vertex has degree three, meaning three edges meet at each vertex. By Steinitz's theorem, such graphs are exactly the simple, 3-connected, planar graphs that are also 3-regular.^[64] These graphs represent the combinatorial structure of the polyhedron's vertices and edges, excluding the faces, and their planarity ensures they can be embedded on a sphere without crossings.^[65] Prominent examples include the tetrahedral graph, which is the complete graph K_4 with 4 vertices and 6 edges, serving as the skeleton of the regular tetrahedron.^[66] The cubical graph, with 8 vertices and 12 edges, forms the 1-skeleton of the cube, a Platonic solid. Another example is the dodecahedral graph, a cubic symmetric graph with 20 vertices and 30 edges, underlying the regular dodecahedron.^[67] These graphs illustrate how cubic polyhedral structures arise in regular polyhedra, where the regularity of faces and vertices aligns with the 3-regularity of the graph. All convex polyhedra, including those with cubic skeletons, satisfy Euler's formula v - e + f = 2, where v is the number of vertices, e the number of edges, and f the number of faces. For cubic graphs, the handshaking lemma gives $3v = 2e, so e = \frac{3v}{2} and substituting yields f = \frac{v}{2} + 2. This relation holds for fullerene-like polyhedra, which are cubic polyhedral graphs with exactly 12 pentagonal faces and the remainder hexagonal, though the focus here remains on their graph-theoretic properties rather than applications. Certain Archimedean solids also possess cubic skeletons. For instance, the truncated tetrahedron, an Archimedean solid with 4 regular hexagonal faces and 4 regular triangular faces, has a 1-skeleton that is a cubic graph on 12 vertices and 18 edges.^[68] Goldberg polyhedra provide further examples of cubic polyhedral graphs, constructed as approximations to spheres using pentagonal and hexagonal faces with trivalent vertices, maintaining icosahedral symmetry and satisfying the Euler characteristic.^[69]

Spatial Embeddings

In spatial graph theory, cubic graphs are realized as trivalent spatial graphs embedded in three-dimensional Euclidean space \mathbb{R}^3, where each vertex has degree three and edges are smooth arcs intersecting only at vertices or via minor crossings along their interiors.^[70] These embeddings generalize classical knot and link theory by allowing the cycles within the graph to form knotted or linked substructures, with equivalence determined by ambient isotopy.^[71] Adapted Reidemeister moves, such as IH-moves, classify such embeddings by permitting local transformations at trivalent vertices and crossings, preserving the topological type.^[72] The stick number of a trivalent spatial graph provides a measure of embedding complexity, defined as the minimum number of straight-line segments (sticks) needed to construct an isotopic polygonal realization without unintended crossings at non-vertices. For the theta-curve—a fundamental trivalent spatial graph with two vertices and three edges—any nontrivial embedding requires at least seven sticks, while almost trivial embeddings (where all subknots are unknotted but linked) demand at least eight.^[73] For instance, the theta-curve containing a trefoil subknot achieves a stick number of seven, illustrating how subdivision of edges enables realization of knotted configurations.^[73] Upper bounds on stick numbers for spatial graphs relate to crossing numbers and other graph parameters.^[74] Examples of spatial embeddings of cubic graphs include the cube graph, realized as the crossing-free skeleton of a cube in \mathbb{R}^3, where all cycles are unknotted and unlinked. More intricate cases arise with the Borromean rings, which emerge as a three-component link formed by cycles in embeddings of certain trivalent graphs; in clasper theory, these rings are resolved into trivalent vertices to compute higher-order linking invariants via configuration spaces.^[75] Such structures highlight non-trivial linking undetectable by pairwise Gauss linking numbers.^[75] The Conway-Gordon theorem demonstrates that embeddings of complete graphs like K_7 always contain odd knots among their Hamiltonian cycles, inspiring analogous results for trivalent spatial graphs where specific embeddings yield cycles with odd Arf invariants.^[76] Unknotting numbers extend to trivalent spatial graphs, quantifying the minimum crossing changes needed to trivialize an embedding. For theta-curves, the unknotting number u(f) equals half the crossing number c(f) if and only if the embedding f is trivial.^[77] In contrast, for handcuff graphs—trivalent spatial graphs consisting of two cycles joined by an edge—u(f) = c(f)/2 holds under conditions like alternating diagrams between the loops, providing bounds on the complexity of knotted components.^[77] These metrics underscore the interplay between geometric realizations and topological invariants in cubic graph embeddings.

Hamiltonicity

Hamiltonian Cycles

A Hamiltonian cycle in a cubic graph is a cycle that visits each vertex exactly once and returns to the starting vertex, thereby spanning the entire graph. In cubic graphs, where every vertex has degree 3, the existence of such cycles is a central topic in graph theory, influenced by the graph's connectivity and other structural properties. Sufficient conditions for Hamiltonicity, such as adaptations of Dirac's and Ore's theorems, provide limited guarantees for larger cubic graphs. Dirac's theorem states that a graph with minimum degree δ ≥ n/2 is Hamiltonian, but for cubic graphs with δ = 3, this only applies to graphs with at most 6 vertices, rendering it a weak condition for typical cases. Similarly, Ore's theorem, which requires that for every pair of non-adjacent vertices u and v, deg(u) + deg(v) ≥ n, simplifies in cubic graphs to the same restrictive bound, confirming Hamiltonicity only for small instances. More robust results emerge for specific subclasses of cubic graphs. For planar cubic graphs, Thomassen's theorem establishes that every 4-connected planar graph is Hamiltonian-connected, meaning there exists a Hamiltonian path between any pair of vertices; this directly implies the existence of a Hamiltonian cycle in 4-connected planar cubic graphs as a special case. In bipartite cubic graphs, which are 3-regular bipartite graphs with equal partition sizes, not all instances are Hamiltonian, as counterexamples exist despite the balanced structure. However, random cubic bipartite graphs are Hamiltonian with high probability, as shown by asymptotic analysis confirming that such graphs possess a Hamiltonian cycle almost surely as the number of vertices grows.^[78] The cycle double cover conjecture connects to Hamiltonicity in cubic graphs by positing a stronger covering property: every bridgeless graph admits a collection of cycles where each edge appears in exactly two cycles. A Hamiltonian cycle serves as a single-cycle cover of the edges, and in cubic graphs, the conjecture's resolution would imply the existence of multiple edge-disjoint cycles whose union doubles the edge coverage, potentially aiding in constructing or verifying Hamiltonian structures through iterative cycle decompositions. Detecting a Hamiltonian cycle in general cubic graphs is NP-complete, even when restricted to planar 3-connected instances,^[79] necessitating exponential-time algorithms for exact solutions, such as dynamic programming over subsets or backtracking with pruning. Heuristic methods, including local search and genetic algorithms, offer practical approximations for large cubic graphs, often succeeding in finding cycles when they exist, though without guarantees of optimality or completeness.

Non-Hamiltonian Cubic Graphs

In 1880, P. G. Tait conjectured that every cubic polyhedral graph—equivalently, every 3-connected planar cubic graph—is Hamiltonian.^[80] This conjecture arose in the context of Tait's investigations into the four-color theorem and edge colorings of planar graphs. However, in 1946, W. T. Tutte constructed a counterexample known as the Tutte graph, a 3-connected planar cubic graph on 46 vertices that contains no Hamiltonian cycle. The proof of non-Hamiltonicity relies on analyzing bridges and fragments in the graph that prevent a cycle from spanning all vertices.^[81] Tait's conjecture spurred further research into Hamiltonicity of restricted cubic graphs, leading to related open problems. In 1969, David W. Barnette conjectured that every 3-connected planar cubic bipartite graph is Hamiltonian.^[82] This remains unresolved, though partial results confirm it for graphs with certain facial structures or small numbers of vertices.^[83] Unlike Tait's case, no counterexamples are known, and the conjecture implies stronger statements about perfect matchings and cycle covers in such graphs.^[84] Hypohamiltonian cubic graphs provide another class of non-Hamiltonian examples, where the graph itself lacks a Hamiltonian cycle, but removing any single vertex yields a Hamiltonian graph. The Petersen graph, a cubic graph on 10 vertices discovered in 1898, is the smallest such example.^[85] For planar cubic hypohamiltonian graphs, the first example was constructed by Carsten Thomassen in 1978 with 105 vertices. More recent constructions have reduced this to 70 vertices for the smallest known cubic planar case, featuring girth 4.^[86] Despite these counterexamples, most cubic graphs are Hamiltonian. In the uniform model of random 3-regular graphs on n vertices, the probability of being Hamiltonian approaches 1 as n \to \infty.^[87] This asymptotic result, established through analysis of random matchings and cycle extensions, highlights that non-Hamiltonian cubic graphs are atypical. Prominent examples of non-Hamiltonian cubic graphs include the Petersen graph, which is symmetric and has girth 5 but no Hamiltonian cycle, as proven by exhaustive case analysis of possible paths.^[88] The Tutte graph serves as the smallest known 3-connected planar counterexample to Tait's conjecture. Additionally, the Horton graph, a 3-connected cubic bipartite planar graph on 96 vertices constructed in 1982, disproves an extension of Tutte's earlier conjecture for bipartite graphs.

Additional Properties

Pathwidth and Width Parameters

Pathwidth is a measure of how well a graph can be decomposed into a path-like structure, with bags of vertices covering the edges in a linear fashion. For cubic graphs, which have maximum degree 3, the pathwidth pw(G) of a graph G with n vertices satisfies pw(G) ≤ (1/6 + ε)n for any ε > 0 and sufficiently large n, as established using separator theorems that recursively partition the graph into smaller components of controlled size.^[89] This upper bound arises from the property that cubic graphs admit balanced separators of size O(n), allowing the construction of path decompositions where the width grows linearly but with a small constant factor. The bound of n/6 is asymptotically tight up to lower-order terms, with known constructions of cubic graphs achieving pathwidth at least (1/12 - o(1))n, based on expander properties of random regular graphs.^[90] The exact optimal constant factor in the linear bound is not resolved. Pathwidth in cubic graphs is closely related to bramble number and haven order, where a bramble of order k implies pw(G) ≥ k - 1, and havens of high order provide dual lower bounds via non-separating choices in linear orderings; these structures highlight the connectivity constraints in bounded-degree graphs. For planar cubic graphs, treewidth tw(G) admits improved bounds over general graphs due to planarity, with tw(G) = O(√n) via separator theorems, though the constant remains larger than for pathwidth in non-planar cases. Examples illustrate these parameters: the Petersen graph, a famous non-planar cubic graph on 10 vertices, has pw(G) = 5, exceeding the average n/6 ≈ 1.67 but fitting within the linear regime for small n.^[91] In contrast, grid-like cubic graphs, such as ladder networks or subdivided meshes made 3-regular, exhibit pathwidth Θ(√n), reflecting their two-dimensional structure and higher local connectivity compared to trees.^[92]

Bipartite Cubic Graphs

A bipartite cubic graph, also known as a bicubic graph, is a 3-regular graph whose vertices can be partitioned into two independent sets of equal size, ensuring balanced connectivity between the partitions. This equality of partition sizes arises because the total number of edges is $3n/2 for n vertices, and since all edges connect the two parts A and B, we have $3|A| = 3|B|, implying |A| = |B|.^[93] Such graphs are necessarily even-order, with no odd cycles, and their structure facilitates symmetric properties like uniform degree distribution across parts. By Hall's marriage theorem, every regular bipartite graph admits a perfect matching, and for cubic bipartite graphs, this extends to a complete 1-factorization into exactly three edge-disjoint perfect matchings that cover all vertices.^[93] This decomposition underscores their utility in matching theory, where the balanced partitions guarantee the existence of such coverings without isolated vertices. As a consequence of bipartiteness, these graphs have chromatic number 2. Not all bipartite cubic graphs are Hamiltonian, though many are; counterexamples include the smallest 3-connected non-Hamiltonian instance, the Georges-Kelmans graph with 50 vertices.^[94] Infinite families of non-Hamiltonian 3-connected cubic bipartite graphs have been constructed, providing ongoing challenges to Hamiltonicity criteria in this class.^[94] Prominent infinite families of bipartite cubic graphs include the cubic cages for even girth, which achieve the minimal order for given degree and girth parameters; it is conjectured that all such cages are bipartite.) The Heawood graph, with 14 vertices and girth 6, is the unique (3,6)-cage and exemplifies symmetric, distance-transitive properties in this family.^[95] Higher even-girth cages, such as the Tutte 8-cage, extend this sequence, highlighting extremal constructions with no shorter cycles. In mathematical applications, bipartite cubic graphs serve as foundational models for expander graphs, where their spectral properties ensure strong connectivity and mixing times. Seminal work shows that a regular bipartite graph expands well if its second-largest eigenvalue is bounded away from the largest, enabling uses in derandomization and error-correcting codes.

Algorithms and Complexity

Enumeration and Generation

The enumeration of cubic graphs up to isomorphism involves generating all non-isomorphic graphs where every vertex has degree 3, typically focusing on connected simple graphs with an even number of vertices (at least 4). Early computational efforts, such as those by Balaban in the 1960s, enumerated all cubic graphs up to 12 vertices using manual and computer-assisted methods. More systematic approaches emerged in the 1980s, with Robinson and Wormald providing counts for connected cubic graphs on up to 16 vertices via backtracking techniques that build graphs by adding edges while pruning isomorphic duplicates.^[96] These methods confirmed small counts, such as 1 connected cubic graph on 4 vertices (the complete graph K_4), 2 on 6 vertices, 5 on 8 vertices, 19 on 10 vertices, and 85 on 12 vertices.^[97] Orderly generation algorithms, which construct graphs in a canonical order to avoid redundancies, have been pivotal for larger enumerations. McKay and Royle applied such an algorithm using backtracking to exhaustively generate and catalog all connected cubic graphs up to 20 vertices, yielding 4060 on 16 vertices and 510489 on 20 vertices, with detailed properties like connectivity and automorphism groups computed for each.^[98] The nauty software suite, developed by McKay, plays a central role in modern enumeration by providing canonical labeling and isomorphism testing, enabling efficient detection of duplicates during generation; it has been integrated into tools like geng for producing non-isomorphic graphs with specified degrees, including cubic ones.^[99] For specialized subclasses, dedicated generators exist. The plantri program by Brinkmann and McKay enumerates 3-connected planar cubic graphs (polyhedral graphs) isomorph-free, producing all such graphs up to thousands of vertices quickly; for example, it generates 1 on 4 vertices, 1 on 6 vertices (the triangular prism), and 2 on 8 vertices.^[100] Recent backtracking-based methods, such as bundled triangle insertion in the snarkhunter tool, extend enumeration to 32 vertices and beyond for connected cubic graphs, leveraging reductions like Δ-Y transformations to build from prime subgraphs while ensuring isomorph-freedom via nauty.^[101] Symmetric cubic graphs, which admit a transitive automorphism group on edges, are enumerated separately in the Foster census, originally compiled by Foster and extended by Conder and Dobcsányi to include all such graphs up to 768 vertices and further to 10,000 vertices in modern databases.^[30] While finite enumerations dominate, infinite families of cubic graphs can be generated constructively using operations like the Δ-Y exchange, which replaces a degree-3 vertex with a triangle or vice versa while preserving regularity, though practical focus remains on bounded sizes due to exponential growth.^[101]

Optimization Problems

Cubic graphs, being 3-regular, present challenging optimization problems due to their bounded degree and structural constraints, often leading to NP-hard or APX-hard complexities even in this restricted class. Key tasks such as finding maximum independent sets, minimum vertex covers, Hamiltonian cycles, proper edge colorings, and recognizing snarks have been extensively studied for their theoretical hardness and algorithmic tractability. The maximum independent set problem in cubic graphs can be solved exactly using dynamic programming techniques that exploit the graph's regularity and low degree. A notable algorithm achieves this in O(2^{n/3}) time by branching on vertices and reducing subproblems based on neighborhood constraints. More advanced measure-and-conquer approaches have improved the exponent for subcubic graphs, yielding runtimes like O(2^{0.288n}), though the problem remains NP-hard. The minimum vertex cover problem is APX-hard on cubic graphs, meaning there is no polynomial-time approximation scheme unless P=NP. This hardness holds even for 3-regular graphs, where the optimal cover size is at least n/2 due to the handshaking lemma, but approximating within a factor better than 7/6 is impossible in polynomial time assuming the unique games conjecture. Standard 2-approximation algorithms via matching apply effectively here, but closing the gap to optimality is computationally intensive. Determining the existence of a Hamiltonian cycle in cubic graphs is NP-complete, as established by a reduction from the general Hamiltonian cycle problem adapted to 3-regular instances.^[3] Despite this, the problem is fixed-parameter tractable when parameterized by solution-specific metrics like the number of non-Hamiltonian components, allowing exponential but sub-2^n time algorithms via bounded search trees tailored to the degree bound. Deciding whether a cubic graph is 3-edge-colorable is NP-complete, directly implying the hardness of edge coloring optimization since bridgeless cubic graphs have chromatic index 3 or 4 by Vizing's theorem. This result underscores the difficulty of scheduling or resource allocation tasks modeled as edge colorings in 3-regular networks. Snark recognition—identifying bridgeless cubic graphs that are not 3-edge-colorable—is coNP-complete, as it is the complement of the 3-edge-colorability decision problem. While polynomial-time algorithms exist for recognizing many subclasses of snarks (e.g., flower snarks), the general case remains hard, with ongoing research exploring structural characterizations to potentially resolve practical instances.

References

[1]
https://dl.acm.org/doi/10.1145/234782.234783
[2]
[PDF] GIRTH SIX CUBIC GRAPHS HAVE PETERSEN MINORS Neil ...
Mar 17, 2014 · A graph is cubic if the degree of every vertex (counting loops twice) is three. The girth of a graph is the length of its shortest circuit, or ...
[3]
The Planar Hamiltonian Circuit Problem is NP-Complete - SIAM.org
We consider the problem of determining whether a planar, cubic, triply-connected graph G has a Hamiltonian circuit. We show that this problem is NP-complete.
[4]
[PDF] Generation of Cubic graphs - HAL Inria
May 13, 2014 · graph theory cubic graphs are the smallest or simplest possible potential counterexamples. In chemistry, cubic graphs serve as models for ...
[5]
Cubic Graph -- from Wolfram MathWorld
Cubic graphs, also called trivalent graphs, are graphs where all nodes have degree 3, and exist only for even n nodes.
[6]
Cubic graph - EPFL Graph Search
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular ...
[7]
[PDF] Solutio problematis ad geometriam situs pertinentis
Sep 25, 2018 · This Article is brought to you for free and open access by the Euler Archive at Scholarly Commons. ... Euler, Leonhard, "Solutio problematis ad ...
[8]
[PDF] arXiv:2005.14031v4 [math.CO] 21 Sep 2021
Sep 21, 2021 · By the handshaking lemma, a cubic graph has an even number of vertices, say 2n, and 3n edges. For k ≥ 2, let f2k be the number of faces bounded ...
[9]
[PDF] The Adjacency Matrix and The nth Eigenvalue 3.1 About these notes ...
Sep 5, 2012 · So, we see that the largest adjacency eigenvalue of a d-regular graph is d, and its corresponding eigenvector is the constant vector. We ...
[10]
[PDF] Matrix techniques for strongly regular graphs and related geometries
It is well-known and easily seen that the adjacency matrix of a k-regular graph has an eigenvalue k with eigenvector. 1 (the all-one vector), and that every ...
[11]
Cycle Graph -- from Wolfram MathWorld
Cycle graphs (as well as disjoint unions of cycle graphs) are two-regular. Cycle graphs are also uniquely Hamiltonian as well as dominating unique. The ...
[12]
Bicubic Graph -- from Wolfram MathWorld
A bicubic graph is a bipartite cubic graph. Tutte (1971) conjectured that all 3-connected bicubic graphs are Hamiltonian (the Tutte conjecture).Missing: definition | Show results with:definition
[13]
[PDF] Bipartite Matching on regular graphs 1 Notation and Definitions
We say a graph is d-regular if every vertex has degree d. Definition 5 (Bipartite Graph). We say a graph is bipartite if there is a partitioning of vertices.
[14]
[PDF] Orthogonal representations of Steiner triple system incidence graphs
Abstract. The unique Steiner triple system of order 7 has a point-block incidence graph known as the. Heawood graph. Motivated by questions in combinatorial ...Missing: original | Show results with:original
[15]
A note on 3-connected cubic planar graphs - ScienceDirect.com
Tutte disproved this conjecture by constructing a non-hamiltonian 3-connected cubic planar graph in [6]. This proves that ...
[16]
Semisymmetric graphs - ScienceDirect.com
... graph, and the Gray graph (the smallest semisymmetric cubic graph). ... It is well-known that the Heawood graph has PGL ( 2 , 7 ) as its 4-regular ...Missing: notable | Show results with:notable
[17]
On the ratio between the maximum weight of a perfect matching and ...
Oct 15, 2021 · In this section we determine the exact value of [Math Processing Error] η for two infinite families of cubic graphs, Prisms and Möbius ladders, ...
[18]
https://arxiv.org/pdf/2410.05422
[19]
Generalizing the generalized Petersen graphs - ScienceDirect.com
Feb 6, 2007 · In this paper, we study a further extension of the notion of GPGs with the emphasis on the symmetry properties of the newly defined graphs.Missing: original | Show results with:original
[20]
[PDF] THEOREMS AND COMPUTATIONS IN CIRCULAR COLOURINGS ...
In particular, we establish the circular chromatic index for several infinite families of snarks, namely Isaacs' flower snarks, Goldberg snarks, and generalized ...
[21]
Four‐terminal reducibility and projective‐planar wye‐delta‐wye ...
Jan 25, 2000 · A graph is YΔY-reducible if it can be reduced to a vertex by a sequence of series-parallel reductions and YΔY-transformations.
[22]
[PDF] A note on constructing large Cayley graphs of given degree and ...
Jul 7, 1997 · Voltage graphs are a powerful tool for constructing large graphs (called lifts) with prescribed properties as covering spaces of small base ...
[23]
https://mathworld.wolfram.com/PetersensTheorem.html
[24]
Petersen's Theorem -- from Wolfram MathWorld
Petersen's theorem states that every cubic graph with no bridges has a perfect matching (Petersen 1891; Frink 1926; König 1936; Skiena 1990, p. 244).
[25]
[PDF] A survey of the cycle double cover conjecture - Brown Math
Jul 2, 2009 · In general, CDC is not known to imply the strong embedding conjecture, but for cubic graphs the two are indeed equivalent: given a list of ...
[26]
Vertex-Transitive Graph -- from Wolfram MathWorld
Informally speaking, a graph is vertex-transitive if every vertex has the same local environment, so that no vertex can be distinguished from any other based on ...
[27]
[PDF] vertex-transitive cubic graphs of square-free order
Introduction. For a graph Γ = (V,E), the number of vertices |V | is called the order of Γ. A graph Γ is called vertex-transitive if its automorphism group ...
[28]
Cubic Vertex-Transitive Graph -- from Wolfram MathWorld
A cubic vertex-transitive graph is a cubic graph that is vertex transitive. Cubic symmetric graphs are a special case of these graphs.
[29]
[PDF] Cubic Vertex-Transitive bi-Cayley Graphs over a Nonabelian Group
The vertex-transitive graph is a graph with high symmetry, and the symmetry of a graph is described by some transitivity properties of the graph. Cayley graph ...
[30]
A032355 - OEIS
Aug 24, 2025 · Number of connected transitive ... cubic vertex-transitive graphs. Gordon Royle, There are 677402 vertex-transitive graphs on 32 vertices.
[31]
Foster Census
This site contains the list of all cubic edge-transitive graphs on at most 10000 vertices. Such a graph can be either vertex-transitive (and thus arc-transitive) ...
[32]
Arc-Transitive Graph -- from Wolfram MathWorld
An arc-transitive graph, sometimes also called a flag-transitive graph, is a graph whose graph automorphism group acts transitively on its graph arcs.
[33]
Arc-Transitive Graphs | Request PDF - ResearchGate
An arc in a graph is an ordered pair of adjacent vertices, and so a graph is arc-transitive if its automorphism group acts transitively on the set of arcs.
[34]
A family of cubical graphs - Cambridge University Press & Assessment
A family of cubical graphs. Published online by Cambridge University Press: 24 October 2008. W. T. Tutte. Show author details. W. T. Tutte: Affiliation:.
[35]
A family of cubical graphs - Semantic Scholar
A family of cubical graphs · W. T. Tutte · Published in Mathematical Proceedings of… 1 October 1947 · Mathematics · Mathematical Proceedings of the Cambridge ...
[36]
[PDF] On cubic vertex-transitive graphs of given girth - Montanuniversität ...
finite connected cubic 3-arc-transitive graphs are the Heawood graph, the Pappus graph, and the Desargues graph. 2 Preliminaries. Let X be a graph. A ...<|control11|><|separator|>
[37]
McGee Graph -- from Wolfram MathWorld
The McGee graph is a cubic symmetric graph on 24 nodes and 36 edges which is the unique 7-cage graph. It can be constructed as the union of the two leftmost ...Missing: arc- | Show results with:arc-
[38]
Gray graph - Wikipedia
The Gray graph is an undirected bipartite graph with 54 vertices and 81 edges. It is a cubic graph: every vertex touches exactly three edges.Missing: paper | Show results with:paper
[39]
Cubic vertex-transitive graphs - SymOmega - WordPress.com
Jan 26, 2012 · Ronald Foster began compiling a list of symmetric cubic graphs in 1932 and this is now known as the Foster census. Marston Conder and Peter ...<|control11|><|separator|>
[40]
[PDF] A more detailed classification of symmetric cubic graphs 1 Introduction
A census of these, including most but not all examples on up to 512 vertices, was compiled by Foster [4], and a complete list of all on up to 768 vertices was ...
[41]
Biggs-Smith Graph -- from Wolfram MathWorld
The Biggs-Smith graph is a cubic symmetric graph with 102 vertices, 153 edges, distance-regular, distance-transitive, and an order-17 expansion of the H graph.
[42]
Distance-transitive graphs admit semiregular automorphisms
Distance-transitive graphs were introduced in 1971 by Biggs and Smith [2], who showed that there are only 12 finite cubic distance-transitive graphs.
[43]
Petersen Graph -- from Wolfram MathWorld
The Petersen graph is the cubic graph on 10 vertices and 15 edges which is the unique (3,5)-cage graph (Harary 1994, p. 175), as well as the unique (3 ...
[44]
Vizing's theorem - PlanetMath
Mar 22, 2013 · Defines, edge coloring ; Defines, edge-k k -coloring ; Defines, chromatic index ; Defines, edge-chromatic number ; Defines, class I.
[45]
Tait coloring - PlanetMath.org
Mar 22, 2013 · A Tait coloring of a trivalent (http://planetmath.org/Valency ) (aka cubic) graph is a coloring of its edges with only three colors, ...
[46]
[PDF] Section 17.3. Snarks
Aug 7, 2022 · We need these ideas for our definition of a snark. Definition. A 4-edge-chromatic essentially 4-edge-connected cubic graph is a snark. Note.
[47]
The NP-Completeness of Edge-Coloring
The cubic graph G is formed from two copies of H by identifying the remaining connecting edges in corresponding pairs. The graph G has a 3-edge-coloring if and ...
[48]
Normal 5-edge-coloring of some snarks superpositioned by Flower ...
Jun 23, 2023 · In this paper, we consider a class of superpositioned snarks obtained by choosing a cycle C in a snark G and superpositioning vertices of C by one of two ...
[49]
Lower bounds on the independence number in terms of the degrees
Wei discovered that the independence number of a graph G is at least Σ v (1 + d(v)) −1. It is proved here that if G is a connected triangle-free graph on n ≥ 3 ...
[50]
A new proof of the independence ratio of triangle-free cubic graphs
Staton proved that every triangle-free graph on n vertices with maximum degree 3 has an independent set of size at least 5n/14. A simpler proof was found by ...
[51]
Vertex Cover -- from Wolfram MathWorld
A vertex cover of a graph G can also more simply be thought of as a set S of vertices of G such that every edge of G has at least one of member of S ...
[52]
Hardnnes of Approximation of Minimum Vertex Cover on 3-Regular ...
Apr 6, 2024 · Indeed, any lower bound for 4-regular graphs can imply one for cubic graphs (using the reduction in doi.org/10.1016/S0304-3975(98)00158-3). If ...
[53]
The Genus Problem for Cubic Graphs - ScienceDirect.com
Abstract. We prove that the following problem is NP-complete: Given a cubic graphGand a natural numberg, is it possible to drawGon the sphere withghandles added ...
[54]
An embedding of the Petersen graph in the torus. - ResearchGate
We define the defect of a graph and use it to study embeddings of superpositions of cubic graphs into orientable surfaces.Missing: toroidal | Show results with:toroidal
[55]
Heawood graph
It is the point-line incidence graph of the Fano plane, and is commonly called the Heawood graph. It occurs as subgraph of the Hoffman-Singleton graph.<|control11|><|separator|>
[56]
[PDF] Embeddings of Small Graphs on the Torus - Computer Science
K7 has one embedding, shown in Figure 12. The dual of K7 on the torus is the Heawood graph, which is the incidence graph of the Fano plane, the 7-point ...
[57]
[PDF] arXiv:2003.05186v1 [math.CO] 11 Mar 2020
Mar 11, 2020 · Cyclic generalised voltage graphs are used both to define as well as analyse the connected, simple, cubic graphs admitting a cyclic group of ...
[58]
3-maps - ScienceDirect.com
It is natural to ask which cubic, bipartite graphs have 3-maps. In fact, they all do. Theorem 3. A connected cubic graph is the underlying graph for some 3-map ...
[59]
Random cubic planar graphs converge to the Brownian sphere
Then, Whitney's theorem ensures that a 3-connected cubic planar graph is the dual of a simple triangulation, for which it is known that the scaling limit is the ...
[60]
K3,3 – Graph Embeddings
K3,3 has an optimal genus of 1, can be embedded using a Cayley map with Z_6 and rotation (1 3 5), and has a face set of two 6-gons.
[61]
Showing genus of a Petersen graph is equal to 1
Feb 25, 2022 · We thus show that the Petersen graph can be embedded in this rectangle where there is only one crossing st the genus is equal to 1.Is there a bound for the genus of the generalized petersen graphs?A periodic layout for the Petersen graph - Math Stack ExchangeMore results from math.stackexchange.com
[62]
Barnette's Conjecture -- from Wolfram MathWorld
Barnette's conjecture asserts that every 3-connected bipartite cubic planar graph is Hamiltonian. The only graph on nine or fewer vertices satisfying Barnette' ...
[63]
Matching theory and Barnette's conjecture - ScienceDirect.com
Barnette's Conjecture claims that all cubic, 3-connected, planar, bipartite graphs are Hamiltonian. We give a translation of this conjecture into the ...
[64]
(PDF) Graphs of Maps - ResearchGate
This work studies certain aspects of graphs embedded on surfaces. Initially, a colored graph model for a map of a graph on a surface is developed.
[65]
Steinitz's Theorem -- from Wolfram MathWorld
Steinitz's Theorem: A graph G is the edge graph of a polyhedron iff G is a simple planar graph which is 3-connected.
[66]
Polyhedral Graph -- from Wolfram MathWorld
An n -polyhedral graph (sometimes called a c -net) is a 3-connected simple planar graph on n nodes. Every convex polyhedron can be represented in the plane ...<|control11|><|separator|>
[67]
Tetrahedral Graph -- from Wolfram MathWorld
The tetrahedral graph is a Platonic graph with 4 nodes, 6 edges, and a diameter of 1. It is also a complete graph (K_4) and a wheel graph (W_4).Missing: K4 | Show results with:K4
[68]
Dodecahedral Graph -- from Wolfram MathWorld
The dodecahedral graph is the skeleton of the great stellated dodecahedron as well as the dodecahedron. It is the cubic symmetric denoted F_(020)A and is ...
[69]
Truncated Tetrahedral Graph -- from Wolfram MathWorld
The truncated tetrahedral graph is the cubic Archimedean graph on 12 nodes and 18 edges that is the skeleton of the truncated tetrahedron.
[70]
[PDF] Goldberg DRAFT - George W. Hart
Goldberg Polyhedra have pentagons and hexagons, trivalent vertices, and icosahedral symmetry. They always contain exactly twelve pentagons.
[71]
[PDF] arXiv:1806.09720v1 [math.GT] 25 Jun 2018
Jun 25, 2018 · A spatial graph is an embedding of a graph into R3. Two spatial graphs are considered the same if there exists an ambient isotopy taking one ...
[72]
The IH-complex of Spatial Trivalent Graphs - Project Euclid
We define the IH-complex on the set of spatial trivalent graphs by using the IH-move, which is a local spatial move appeared in a study of knotted handlebodies.
[73]
Moves and invariants for knotted handlebodies - MSP
Sep 3, 2008 · The first aim of this paper is to introduce moves for spatial trivalent graphs, called IH-moves, and show that two spatial trivalent graphs are ...<|separator|>
[74]
[PDF] STICK NUMBER OF THETA-CURVES Youngsik Huh and ...
The equivalence, triviality and stick presentation of θ-curves can be defined in the same way as knots. The θ-graph contains three cycles. Therefore a θ-curve ...
[75]
None
### Summary of Stick Number for Spatial Graphs, Trivalent/Cubic Graphs, and Examples
[76]
Borromean rings and linkings - ScienceDirect.com
For links of 3 components, such as Borromean rings, which escape the detection of Gauss linking, we define and compute combinatorically and explicitly the ...
[77]
[PDF] Knots and links in spatial graphs
Theorem 2. Every spatial embedding of K, contains a nontrivial knot. The proofs actually yield more specific information. Precisely, every spatial embedding of ...
[78]
[PDF] arXiv:2103.11079v1 [math.GT] 20 Mar 2021
Mar 20, 2021 · Abstract. We study relations between unknotting number and crossing number of a spatial embedding of a handcuff-graph and a theta curve.
[79]
Tait's Hamiltonian Graph Conjecture -- from Wolfram MathWorld
Tait's Hamiltonian graph conjecture asserted that every cubic polyhedral graph is Hamiltonian. It was proposed by Tait in 1880 and refuted by Tutte (1946).
[80]
Where is the proof of Tutte's graph having no Hamiltonian cycles?
Oct 31, 2018 · This is absurd. Thus there are no Hamiltonian cycles in the Tutte graph, which is easily seen to be cubic and planar, completing the proof.
[81]
[1310.5504] Barnette's Conjecture - arXiv
Oct 21, 2013 · This report provides an overview of theorems and statements related to a conjecture stated by D.W. Barnette in 1969 (which is an open problem ...
[82]
On Barnette's conjecture - ScienceDirect.com
Barnette's conjecture is the statement that every cubic 3-connected bipartite planar graph is Hamiltonian. We show that if such a graph has a 2-factor F ...
[83]
[2202.11641] Matching Theory and Barnette's Conjecture - arXiv
Feb 23, 2022 · Barnette's Conjecture claims that all cubic, 3-connected, planar, bipartite graphs are Hamiltonian. We give a translation of this conjecture ...
[84]
[PDF] Small Hypohamiltonian Graphs
the Petersen graph is the smallest hypohamiltonian graph. ... The same method as above, beginning directly at Phase Two, is quite fast at finding the cubic ...
[85]
[2403.18384] Small planar hypohamiltonian graphs - arXiv
Mar 27, 2024 · Until now, the smallest known planar hypohamiltonian graph had 40 vertices, a result due to Jooyandeh, McKay, Östergård, Pettersson, and ...
[86]
Almost all cubic graphs are Hamiltonian - Wiley Online Library
At least 98.4% of large labelled cubic graphs are hamiltonian. In the present article, this is improved to 100% in the limit by asymptotic analysis.
[87]
Almost All Cubic Graphs Are Hamiltonian - Semantic Scholar
Almost All Cubic Graphs Are Hamiltonian · R. W. Robinson, N. Wormald · Published in Random Struct. Algorithms 1 March 1992 · Mathematics · Random Struct. Algorithms.
[88]
Pathwidth of cubic graphs and exact algorithms - ScienceDirect
Based on this bound we improve the worst case time analysis for a number of exact exponential algorithms on graphs of maximum vertex degree three.
[89]
Pathwidth of cubic graphs and exact algorithms - ResearchGate
Aug 6, 2025 · We prove a general reduction theorem which allows us to extend bounds for certain graph parameters on cubic graphs to bounds for general graphs ...
[90]
Vertex separation - Graph Theory - SageMath Documentation
The pathwidth of a Petersen graph is 5: Sage. sage: g = graphs.PetersenGraph ... graphs and the pathwidth of undirected graphs proposed in [CMN2014].
[91]
Lower bounds on the pathwidth of some grid-like graphs
Mar 1, 2008 · We present proofs of lower bounds on the node search number of some grid-like graphs including two-dimensional grids, cylinders, ...Missing: cubic | Show results with:cubic
[92]
[PDF] 3 Matchings
Perfect Matchings: A matching M is perfect if it covers every vertex. Corollary 3.3 Every regular bipartite graph has a perfect matching. Proof: Let G be a k- ...
[93]
Heawood Graph -- from Wolfram MathWorld
The Heawood graph is a cubic graph on 14 vertices and 21 edges which is the unique (3,6)-cage graph. It is also a Moore graph.
[94]
https://arxiv.org/abs/2101.00943
[95]
A002851 - OEIS
Sep 20, 2025 · Connected 3-regular simple graphs with girth at least g: A185131 (triangle); chosen g: this sequence (g=3), A014371 (g=4), A014372 (g=5), A014374
[96]
[PDF] Constructina the cubic araphs on up to 20 vertices.
All the non-isomorphic, connected cubic graphs on up to 20 vertices are found by this method, and catalogued with the graph theoretic properties of connectivity ...
[97]
The nauty Traces page
There is a suite of programs called gtools included in the nauty package. For example, geng can generate non-isomorphic graphs very quickly.
[98]
[PDF] Fast generation of planar graphs
The program plantri is the fastest isomorph-free generator of many classes of planar graphs, including triangulations, quadrangulations, and convex ...
[99]
[PDF] Generation of Cubic graphs
graph theory cubic graphs are the smallest or simplest possible potential counterexamples. ... Lemma 2.2 The class of prime graphs can be generated from K4 ...