Evendegree

Evendegree is a term used in graph theory to describe a property of undirected graphs in which every vertex has an even degree. The degree of a vertex is the number of edges incident to it, and evendegree means that this number is even for every vertex in the graph. If the graph is disconnected, the condition applies to each connected component, so a graph is said to have evendegree if all of its components have this property.

Formally, a finite graph G = (V, E) has evendegree if deg(v) is even for all v in V. This condition implies that isolated vertices (degree zero) are allowed, since zero is even. A graph with evendegree may consist of one or more connected components, each of which is Eulerian, meaning it contains a closed trail that uses every edge of that component exactly once.

A key consequence is the Euler circuit criterion: a connected graph has an Euler circuit if and only if every vertex has even degree. Consequently, every component of an evendegree graph can be decomposed into edge-disjoint cycles that cover all edges. This decomposition provides practical methods for traversing the graph and for understanding its structure.

Evendegree is often identified in algorithms that seek Euler tours, cycle decompositions, or optimizations related to route planning. It is also used conceptually in proofs and discussions about parity in graphs, network design, and combinatorial constructions.

See also: degree, Eulerian path, Eulerian circuit, cycle decomposition, parity in graphs.