Regular graph

This article defines a property that can be evaluated to true/false for any undirected graph, and is invariant under graph isomorphism. Note that the term "undirected graph" as used here does not allow for loops or parallel edges, so there can be at most one edge between two distinct vertices, the edge is completely described by the vertices it joins, and there can be no edge from a vertex to itself.
View other such properties

Definition

For finite degrees

Suppose $d$ is a nonnegative integer. An undirected graph is termed $d$-regular or degree-regular if it satisfies the following equivalent definitions:

1. The degrees of all vertices of the graph are equal to $d$. Note that $d$ must be strictly less than the total number of vertices in the graph.
2. The adjacency matrix of the graph is $d$ times a doubly stochastic matrix.

Note that if the graph is a finite graph, then we need only concern ourselves with the definition above for finite degrees.

For arbitrary degrees

Suppose $G$ is a graph and $\alpha ,\beta$ are cardinals such that $\alpha +\beta +1$ equals the number of vertices in $G$. Then, $G$ is regular for the pair $(\alpha ,\beta )$ if the degree of every vertex in $G$ is $\alpha$ and the degree of every vertex in the complement of $G$ is $\beta$.

Note that if $\alpha$ is finite, this reduces to the definition in the finite case.

Particular cases

Condition on number of vertices	Condition on degree	What can we say about the graph?	Number of isomorphism classes possible after fixing number of vertices and degree
any	0	empty graph (graph with no edges)	1
2	1	2-clique (two vertices with an edge joining them)	1
even or infinite	1	matching graph: a disjoint union of 2-cliques	1
odd finite	1	no possibility	0
finite number $n$	2	union of pairwise disjoint cyclic graphs with cycle lengths of size at least three	number of unordered integer partitions where all parts are at least 3
infinite	2	union of pairwise disjoint cyclic graphs and chains extending infinitely in both directions	infinite
finite number $n$	$n-1$	complete graph (i.e., clique) on $n$ vertices)	1
finite number $n$	$n-2$	complement of a matching graph	1

Relation with other properties

Stronger properties

Property	Meaning	Proof of implication	Proof of strictness (reverse implication failure)	Intermediate notions
vertex-transitive graph	automorphism group is transitive on vertex set	vertex-transitive implies regular	regular not implies vertex-transitive, regular connected not implies vertex-transitive	Template:Intermediate notion short
empty graph	no edges			Symmetric graph|FULL LIST, MORE INFO
complete graph	every pair of vertices is adjacent			Symmetric graph|FULL LIST, MORE INFO

Metaproperties

Metaproperty name	Satisfied?	Proof	Statement
complementation-closed graph property	Yes	complement of regular graph is regular	The complement of a regular graph is regular. In the finite case, the complement of a $d$-regular $n$-vertex graph is $(n-1-d)$-regular.