Degree (graph theory, $\mathrm{deg}(v)$)

The degree of a vertex is the number of edges incident with it, equivalently the cardinality of its neighbourhood in a simple graph.

The degree sequence of a labelled graph records the degree of a vertex at each label. The handshaking lemma gives ${\sum }_i{d}_i=2|E|$. 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 $\overline{d}(G)=2e(G)/|V(G)|$. It lies between the minimum degree of a graph and the maximum degree of a graph.

A graph is $d$-regular when every vertex has degree $d$.

An $r$-regular graph is class two when its edge chromatic number exceeds $r$. For a finite simple graph, Vizing's theorem makes that edge chromatic number exactly $r+1$. An $r$-colour proper edge colouring of an $r$-regular graph would partition its edges into $r$ perfect matchings, since every vertex would see each colour exactly once.

Let $p$ be prime and set $s=2p-2$. If a bipartite graph has edge-disjoint perfect matchings $M_0,\dots ,M_{\sigma -1}$ on nested nonempty vertex sets, and $|V(M_{i+s})|>s|V(M_i)|/(s+1)$, then the union of $s+1$ consecutive matchings in a graph has maximum degree at most $2p-1$ and more than $(p-1)|V(M_i)|$ edges. The prime-regular subgraph from Boolean polynomial constraints gives a $p$-regular subgraph. Its perfect matching decomposition gives a $k$-regular subgraph for every $k\le p$. If none exists, every $s$ steps shrink the vertex set by factor at most $s/(s+1)$, bounding $\sigma$ by a constant times $\log n$.

For fixed $r,\ell \ge 3$ and $rn$ 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 $(n{)}_{\ell }[r(r-1){]}^{\ell }/[2\ell {\prod }_{j=0}^{\ell -1}(rn-2j-1)]$. Conditioning on the chosen cycle leaves degrees $r-2$ at its vertices and $r$ elsewhere; forbid further edges along that cycle. The bounded-degree pairing avoidance estimate changes by $o(1)$, 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 $A^2+A-2I=J$ and has eigenvalues $3,1,-2$ of multiplicities $1,5,4$.

If $A$ is the adjacency matrix of a $d$-regular graph and $\mathbf{e}=(1,\dots ,1{)}^T$, every row sum of $A$ is $d$, soIf the graph is connected, the $d$-eigenspace is exactly $\mathrm{span}\{\mathbf{e}\}$.

A connected regular graph has exactly two distinct adjacency eigenvalues if and only if it is a complete graph $K_n$ with $n\ge 2$. Its eigenvalues are $n-1$ on the constant vectors and $-1$ on their orthogonal complement.

In a finite graph with at least one edge, the degree-biased vertex distribution assigns probability proportional to the degree of a vertex. It is the distribution of an endpoint on a specified side of a uniformly random edge.

A universal vertex is adjacent to every other vertex of its graph.

The minimum degree $\delta (G)$ is the least degree of a vertex of $G$.

The minimum degree is $\delta (G)={\min }_{v\in V(G)}\mathrm{deg}(v)$, the least degree of a vertex in the graph.

The maximum degree $\Delta (G)$ is the greatest degree of a vertex of $G$.

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 connected graph vertex sets whose union is the whole graph vertex set. In a locally finite graph, every prescribed finite graph path together with all graph neighbours of its visited graph 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.