Bivariegated graph

In graph theory, a bivariegated graph is a graph whose vertex set can be partitioned into two equal parts such that each vertex is adjacent to exactly one vertex from the other set not containing it.

[1][2][3] In a bivarigated graph G with 2n vertices, there exists a set of n independent edges such that no odd number of them lie on a cycle of G. The Petersen graph, shown below, is a bivariegated graph: if one partitions it into an outer pentagon and an inner five-point star, each vertex on one side of the partition has exactly one neighbor on the other side of the partition.

More generally, the same is true for any generalized Petersen graph formed by connecting an outer polygon and an inner star with the same number of points; for instance, this applies to the Möbius–Kantor graph and the Desargues graph.

A tree T with 2n vertices, is bivariegated if and only if the independence number of T is n, or, equivalently, if and only if it has a perfect matching.

[1] The k-varigated graph, k ≥ 3, can be defined similarly.