Define regular graph with example

A regular graph is a simple graph in which every vertex has the same degree. If every vertex has degree k, it is called k-regular.

Properties:

• A k-regular graph on n vertices has nk/2 edges (by the handshaking theorem), so n·k must be even.
• A 0-regular graph has no edges, a 1-regular graph is a perfect matching, and a 2-regular graph is a disjoint union of cycles.

Examples:

• Cₙ (cycle) is 2-regular; C₄ is the square.
• Kₙ (complete graph) is (n − 1)-regular; K₄ is 3-regular with 6 edges.
• Q₃ (cube) is 3-regular with 8 vertices and 12 edges.
• The Petersen graph is 3-regular on 10 vertices.

  a ------ b          every vertex has degree 2
  |        |          (2-regular, n = 4, edges = 4·2/2 = 4)
  d ------ c

This is C₄. In contrast, the path P₃ (a–b–c) is not regular, since the end vertices have degree 1 and the middle one has degree 2.