In the mathematical field of graph theory, a cubic graph is a graph where all vertices have degree 3. In other words a cubic graph is a 3-regular graph. Euclid, detail from The School of Athens by Raphael. ... A labeled graph with 6 vertices and 7 edges. ... This article just presents the basic definitions. ... In graph theory, the degree (or valency) of a vertex is the number of edges incident to the vertex. ... In graph theory, a regular graph is a graph where each vertex has the same number of neighbors, i. ...

A bicubic graph is a cubic bipartite graph. In the mathematical field of graph theory, a bipartite graph is a special graph where the set of vertices can be divided into two disjoint sets with two vertices of the same set never sharing an edge. ...

In 1880, P.G. Tait conjectured that every cubic graph has a Hamiltonian circuit. William Thomas Tutte provided a counter-example, a 46-vertex graph now named for him, in 1946. 1880 (MDCCCLXXX) was a leap year starting on Thursday (see link for calendar). ... Peter Tait Peter Guthrie Tait (April 28, 1831 - July 4, 1901) was a Scottish mathematical physicist. ... In the mathematical field of graph theory, a Hamiltonian path is a path in a undirected graph which visits each vertex exactly once. ... William Thomas Tutte (May 14, 1917 - May 2, 2002) was a British codebreaker and mathematician. ... 1946 (MCMXLVI) was a common year starting on Tuesday. ...

In 1971, Tutte conjectured that all bicubic graphs are Hamiltonian. However, Horton provided a 96-vertex counterexample. 1971 (MCMLXXI) was a common year starting on Friday (the link is to a full 1971 calendar). ... In the mathematical field of graph theory, a Hamiltonian path is a path in a undirected graph which visits each vertex exactly once. ...

In 2003, Petr Hliněný showed that the problem of finding the crossing number (the minimum number of edges which cross in any graph drawing) of a cubic graph is NP-hard, despite the fact that they have low degree. There are, however, practical approximation algorithms for finding the crossing number of cubic graphs. 2003 (MMIII) was a common year starting on Wednesday of the Gregorian calendar. ... In mathematics, crossing numbers arise in two related contexts: in knot theory and in graph theory. ... In computational complexity theory, NP-hard (Non-deterministic Polynomial-time hard) refers to the class of decision problems that contains all problems H such that for all decision problems L in NP there is a polynomial-time many-one reduction to H. Informally this class can be described as containing... In computer science, approximation algorithms are an approach to attacking NP-hard optimization problems. ...

See also

• Petersen graph
• Snarks

The Petersen graph Another drawing of the Petersen graph, with only two crossings Another drawing, with each edge the same length The Petersen graph is a small graph that serves as a useful example and counterexample in graph theory. ... In graph theory, a snark is a connected, bridgeless cubic graph with chromatic index equal to four. ...

References

• Weisstein, Eric W., et al. "Tait's Hamiltonian Graph Conjecture". Accessed April 23, 2005.
• Weisstein, Eric W., et al. "Bicubic graphs". Accessed April 23, 2005.
• Petr Hliněný. Crossing Number Is Hard for Cubic Graphs. MFCS 2004: 772-782. 2003.