2graph

Two-graph, often written as 2graph in some sources, is a concept from combinatorics and graph theory. On a finite vertex set V, a two-graph is a collection B of 3-element subsets of V such that for every 4-element subset {a, b, c, d} of V, the number of 3-sets from B contained in {a, b, c, d} is even. This parity condition is the defining property of a two-graph.

A standard way to construct a two-graph is from a simple graph G on the same vertex set V. Define B(G) to be the set of triples {x, y, z} for which the subgraph G[{x, y, z}] has an odd number of edges. The pair (V, B(G)) is a two-graph. Conversely, every two-graph arises from some graph in this manner, up to Seidel switching, which changes a graph by toggling adjacency between a chosen vertex’s neighborhood and its complement.

Seidel switching is a central concept: given a graph G and a subset X of vertices, for any edge between a vertex in X and a vertex outside X, the edge is flipped (present becomes absent, absent becomes present); edges within X and within its complement remain unchanged. Two graphs related by a sequence of such switchings belong to the same switching class, and all graphs in a class determine the same two-graph.

Two-graphs are studied for their connections to switching theory, strongly regular graphs, and finite geometry, and they serve as a compact invariant encoding graph-structural information. The term 2graph is a less common alias for this object; the standard term is two-graph.