Regular graph: Difference between revisions

Revision as of 19:35, 27 May 2012

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

An undirected graph is termed regular or degree-regular if the degrees of all vertices of the graph are equal. Here, the degree of a vertex refers to the number of vertices adjacent to it.

More specifically, if the value of degree is $d$ , we say that the graph is $d$ -regular.

Note that $d$ must be strictly less than the total number of vertices in the graph.

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

@@ Line 26: / Line 26: @@
 | infinite || 2 || union of pairwise disjoint cyclic graphs and chains extending infinitely in both directions || infinite
 |-
-| finite number <math>n</math> || <math>n - 1</math> || [[complete graph]] (i.e., clique) on <math>n</math> vertices)
+| finite number <math>n</math> || <math>n - 1</math> || [[complete graph]] (i.e., clique) on <math>n</math> vertices) || 1
 |}