The degree of a vertex is the number of incident edge ends in an undirected graph, counting a self-loop twice. Parallel edges contribute separately. In a simple graph, this equals the cardinality of the graph neighbourhood . Thus a vertex with one self-loop and no other edges has degree two, whereas a leaf of a graph has degree one. Counting these incidences at every vertex gives the handshaking lemma .
The in-degree of a vertex in a directed graph is the number of edges directed into it, counting multiplicities when parallel edges are allowed. A directed loop contributes one to both the in-degree and the outdegree.
For edges , , and , the vertex has in-degree two and outdegree one. In every finite directed graph, the sum of the in-degrees equals the number of edges, since every edge has exactly one destination. It also equals the sum of the outdegrees.
The degree sequence of a labelled graph records the degree of a vertex at each label. The handshaking lemma gives . A nonincreasing list forgets the assignment of degrees to labels unless a particular ordering is specified.
The number of edges of a directed graph directed away from a given vertex. Assigning directions to undirected edges is an orientation of a graph.
The average vertex degree of a graph is the sum of its vertex degrees divided by its order. Double counting edge endpoints gives . It lies between the minimum degree of a graph and the maximum degree of a graph.
A graph is -regular when every vertex has degree .
An -regular graph is class two when its edge chromatic number exceeds . For a finite simple graph, Vizing's theorem makes that edge chromatic number exactly . An -colour proper edge colouring of an -regular graph would partition its edges into perfect matchings, since every vertex would see each colour exactly once.
Let be prime and set . If a bipartite graph has edge-disjoint perfect matchings on nested nonempty vertex sets, and , then the union of consecutive matchings in a graph has maximum degree at most and more than edges. The prime-regular subgraph from Boolean polynomial constraints gives a -regular subgraph. Its perfect matching decomposition gives a -regular subgraph for every . If none exists, every steps shrink the vertex set by factor at most , bounding by a constant times .
For fixed and even, a prescribed graph cycle in the configuration model has two ordered distinct half-edges at each of its vertices. Therefore its expected count is . Conditioning on the chosen cycle leaves degrees at its vertices and elsewhere; forbid further edges along that cycle. The bounded-degree pairing avoidance estimate changes by , so the simplicity probability conditional on the cycle divided by the unconditional probability tends to one. The displayed expectation therefore holds for the uniform simple graph, not just the unconditioned pairing model.
The graph whose vertices are two-element subsets of a five-element set, with two vertices adjacent when the subsets are disjoint. It has ten vertices, degree three, zero common neighbours for adjacent pairs and one for nonadjacent pairs. Its adjacency matrix of a graph satisfies and has eigenvalues of multiplicities .
If is the adjacency matrix of a -regular graph and , every row sum of is , so
If the graph is connected, the -eigenspace is exactly .
A connected regular graph has exactly two distinct adjacency eigenvalues if and only if it is a complete graph with . Its eigenvalues are on the constant vectors and on their orthogonal complement.
For a finite undirected graph with edges, the degree-biased probability distribution is
Choose an edge uniformly, then choose one of its two endpoint incidences uniformly. A vertex is selected once for each incident edge end, so the handshaking lemma normalizes the probabilities. For the three-vertex path graph, the probabilities are .
In a bipartite graph, choosing only the endpoint in one specified part instead gives on that part and zero on the other. This conditional sampling convention differs from the probability distribution on the whole vertex set.
A universal vertex is adjacent to every other vertex of its graph.
The minimum degree is , the least degree of a vertex in the graph.
It is the maximum of the degree of a vertex over all vertices.
A graph is locally finite when every vertex has finite degree.
A tree in which every vertex has finitely many incident edges; for a rooted tree this is equivalent to finitely many children per node. Induction on depth then shows every level from a single root is finite, even if the entire tree is infinite. Consequently ordinary breadth-first tree search can eventually reach each node, provided the elementary traversal operations terminate.
An exhaustion of a countable graph is an increasing sequence of finite vertex sets whose union is the whole vertex set. Enumerating the vertices and taking finite initial segments gives one. The induced finite subgraphs need not be connected graph.
For a connected graph that is a locally finite graph, the graph balls about a fixed vertex give a connected exhaustion: each ball is finite, and every vertex has finite graph distance from the centre. In a locally finite graph, any prescribed finite graph path, together with all graph neighbours of its visited vertices, lies in a sufficiently large exhaustion set. This permits coupling finite-volume and infinite-volume simple random walks up to a finite stopping time. A disconnected graph cannot have an exhaustion by connected vertex sets covering different connected components of a graph.

Articles by others on the same topic (1)