Quartic graph

Examples

Several well-known graphs are quartic. They include:

• The complete graph K5, a quartic graph with 5 vertices, the smallest possible quartic graph.
• The Chvátal graph, another quartic graph with 12 vertices, the smallest quartic graph that both has no triangles and cannot be colored with three colors.{{citation
• The Folkman graph, a quartic graph with 20 vertices, the smallest semi-symmetric graph.{{citation
• The Meredith graph, a quartic graph with 70 vertices that is 4-connected but has no Hamiltonian cycle, disproving a conjecture of Crispin Nash-Williams.{{citation

Every medial graph is a quartic plane graph, and every quartic plane graph is the medial graph of a pair of dual plane graphs or multigraphs.{{citation

Properties

Because the degree of every vertex in a quartic graph is even, every connected quartic graph has an Euler tour. And as with regular bipartite graphs more generally, every bipartite quartic graph has a perfect matching. In this case, a much simpler and faster algorithm for finding such a matching is possible than for irregular graphs: by selecting every other edge of an Euler tour, one may find a 2-factor, which in this case must be a collection of cycles, each of even length, with each vertex of the graph appearing in exactly one cycle. By selecting every other edge again in these cycles, one obtains a perfect matching in linear time. The same method can also be used to color the edges of the graph with four colors in linear time.{{citation

Quartic graphs have an even number of Hamiltonian decompositions.{{citation

Open problems

It is an open conjecture whether all quartic Hamiltonian graphs have an even number of Hamiltonian circuits, or have more than one Hamiltonian circuit. The answer is known to be false for quartic multigraphs.{{citation

References