Editing Regular graph (section)

== Existence ==

The necessary and sufficient conditions for a <math>k</math>-regular graph of [[Glossary of graph theory#order|order]] <math>n</math> to exist are that <math> n \geq k+1 </math> and that <math> nk </math> is even.

Proof: A [[complete graph]] has every pair of distinct vertices connected to each other by a unique edge. So edges are maximum in complete graph and number of edges are <math>\binom{n}{2} = \dfrac{n(n-1)}{2}</math> and degree here is <math>n-1</math>. So <math>k=n-1,n=k+1</math>. This is the minimum <math>n</math> for a particular <math>k</math>. Also note that if any regular graph has order <math>n</math> then number of edges are <math>\dfrac{nk}{2}</math> so <math>nk</math> has to be even.
In such case it is easy to construct regular graphs by considering appropriate parameters for [[circulant graph]]s.