Half graph
= Half graph
{wiki}
A half graph has two <vertex> classes $X=\{x_1,\ldots,x_n\}$ and $Y=\{y_1,\ldots,y_n\}$, with $x_i$ adjacent to $y_j$ exactly when $i\leq j$. Its nested <vertex neighbourhoods> give a useful obstruction to partitions in which every pair is a <regular pair of vertex sets>.