# Regular graph

From 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

## Contents

## Definition

### For finite degrees

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

- The degrees of all vertices of the graph are equal to . Note that must be strictly less than the total number of vertices in the graph.
- The adjacency matrix of the graph is 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 is a graph and are cardinals such that equals the number of vertices in . Then, is regular for the pair if the degree of every vertex in is and the degree of every vertex in the complement of is .

Note that if 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 | 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 | complete graph (i.e., clique) on vertices) | 1 | |

finite number | 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 -regular -vertex graph is -regular. |