Regular graph

A graph in which every vertex has the same degree. A graph with degree k at every vertex is called k-regular.

Graph theory: The mathematical study of graphs, structures made of vertices joined by edges. Regular graphs are a basic class within the broader study of graphs.
Handshaking lemma: The theorem that the sum of vertex degrees in a finite undirected graph equals twice its number of edges. It gives the edge count of a finite k-regular graph as k times the vertex count divided by two.
Ramanujan graph: A regular graph whose nontrivial adjacency eigenvalues satisfy a sharp bound related to its degree. These highly expanding regular graphs combine uniform degree with strong connectivity.
Irregular graph: A graph whose vertices do not all have the same degree. It is the direct opposite of a regular graph's defining degree condition.
Vertex degree: The number of edges incident to a vertex, with loops counted twice in standard undirected graphs. A graph is regular precisely when every vertex has equal degree.
Incidence matrix: A matrix encoding which vertices are incident to which edges in a graph. Its structure captures how a fixed degree is distributed across every vertex.
Expander graph: A sparse graph in which every sufficiently small vertex set has a large boundary. Regular expanders provide uniform-degree networks with robust connectivity.
Biregular graph: A bipartite graph in which vertices in each part have a fixed degree, potentially different between parts. It relaxes one common degree into two part-specific degrees.
Adjacency matrix: A matrix recording which pairs of vertices in a graph are adjacent. Its row sums equal vertex degrees, making regularity visible algebraically.
Spectral graph theory: The study of graphs through eigenvalues of matrices associated with them. Regularity gives the adjacency matrix a simple eigenvalue tied directly to the common degree.

Linked from 5 pages