antifactor

Antifactor is a term used in graph theory to denote a spanning subgraph whose vertex degrees complement those of a prescribed factor, relative to the degrees in the original graph. More precisely, for a finite undirected graph G = (V, E) and a function f: V → Z≥0 with f(v) ≤ deg_G(v), an f-factor is a spanning subgraph H ⊆ G with deg_H(v) = f(v) for all v. An anti-factor with respect to f is a spanning subgraph A ⊆ G with deg_A(v) = deg_G(v) − f(v) for all v. If H is an f-factor, then G \ H is its anti-factor.

Existence and theory: The study of f-factors is central in graph factorization, with Tutte’s f-factor theorem giving necessary and sufficient conditions for the existence of an f-factor. Consequently, anti-factors exist exactly when the corresponding f-factor exists, since the edge set G \ H yields an anti-factor with degrees deg_G(v) − f(v). In some texts, antifactor is used simply to mean the complement edge subgraph relative to a chosen f-factor.

Examples and variants: A simple illustration occurs in the complete graph K4, where deg_G(v) = 3 for all v. If f(v) = 1, there exists an f-factor (a perfect matching). Its anti-factor G \ H has deg_G(v) − 1 = 2 at every vertex, forming a 4-cycle. This example shows the direct relationship between a factor and its anti-factor. In literature, antifactor and the complementary f-factor are sometimes used interchangeably; in other sources, antifactor refers more generally to the edge-substructure opposite to a prescribed factor.

See also: factor, f-factor theorem, graph factorization.