Regular Graph

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other. A regular graph with vertices of degree k is called a k‑regular graph or regular graph of degree k.

Regular graphs of degree at most 2 are easy to classify: A 0-regular graph consists of disconnected vertices, a 1-regular graph consists of disconnected edges, and a 2-regular graph consists of disconnected cycles and infinite chains.

A 3-regular graph is known as a cubic graph.

A strongly regular graph is a regular graph where every adjacent pair of vertices has the same number l of neighbors in common, and every non-adjacent pair of vertices has the same number n of neighbors in common. The smallest graphs that are regular but not strongly regular are the cycle graph and the circulant graph on 6 vertices.

The complete graph is strongly regular for any .

A theorem by Nash-Williams says that every k‑regular graph on 2k + 1 vertices has a Hamiltonian cycle.

  • 0-regular graph

  • 1-regular graph

  • 2-regular graph

  • 3-regular graph

Read more about Regular Graph:  Existence, Algebraic Properties, Generation

Famous quotes containing the words regular and/or graph:

    “He hung out of the window a long while looking up and down the street. The world’s second metropolis. In the brick houses and the dingy lamplight and the voices of a group of boys kidding and quarreling on the steps of a house opposite, in the regular firm tread of a policeman, he felt a marching like soldiers, like a sidewheeler going up the Hudson under the Palisades, like an election parade, through long streets towards something tall white full of colonnades and stately. Metropolis.”
    —John Dos Passos (1896–1970)

    “When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
    —Marshall McLuhan (1911–1980)