a 1-dimensional CW complex, cubic graphs are generic in that most 1-cell attaching maps are disjoint from the 0-skeleton of the graph. Cubic graphs are also formed as the graphs of simple polyhedra in three dimensions, polyhedra such as the regular dodecahedron with the property that three faces meet at every vertex. An arbitrary graph embedding on a two-dimensional surface may be represented as a cubic graph structure known as a graph-encoded map. In this structure, each vertex of a cubic graph represents a flag of the embedding, a mutually incident triple of a vertex, edge, and face of the surface. The three neighbors of each flag are the three flags that may be obtained from it by changing one of the members of this mutually incident triple and leaving the other two members unchanged. Hamiltonicity There has been much research on Hamiltonicity of cubic graphs. In 1880, P.G. Tait conjectured that every cubic polyhedral graph has a Hamiltonian circuit. William Thomas Tutte provided a counter-example to Tait's conjecture, the 46-vertex Tutte graph, in 1946. In 1971, Tutte conjectured that all bicubic graphs are Hamiltonian. However, Joseph Horton provided a counterexample on 96 vertices, the Horton graph. Later, Mark Ellingham constructed two more counterexamples: the Ellingham–Horton graphs. Barnette's conjecture, a still-open combination of Tait's and Tutte's conjecture, states that every bicubic polyhedral graph is Hamiltonian. When a cubic graph is Hamiltonian, LCF notation allows it to be represented concisely. If a cubic graph is chosen uniformly at random among all n-vertex cubic graphs, then it is very likely to be Hamiltonian: the proportion of the n-vertex cubic graphs that are Hamiltonian tends to one in the limit as n goes to infinity. David Eppstein conjectured that every n-vertex cubic graph has at most 2n/3 (approximately 1.260n) distinct Hamiltonian cycles, and provided examples of cubic graphs with that many cycles. The best proven estimate for the number of distinct Hamiltonian cycles is . Other properties The pathwidth of any n-vertex cubic graph is at most n/6. The best known lower bound on the pathwidth of cubic graphs is 0.082n. It is not known how to reduce this gap between this lower bound and the n/6 upper bound. It follows from the handshaking lemma, proven by Leonhard Euler in 1736 as part of the first paper on graph theory, that every cubic graph has an even number of vertices. Petersen's theorem states