A cograph (or "complement-reducible graph") is a finite simple graph obtainable from the singleton graph by repeated application of the following rules:
1. The singleton graph 
is a cograph,
2. If 
is a cograph, then so is its graph
complement, and
3. If 
and 
are cographs, then so is their graph
disjoint union.
(Brandstädt et al. 1999).
Cographs have been discovered independently under several definitions and names (Corneil et al. 1981, Brandstädt et al. 1999).
For a finite simple graph 
with at least one graph
vertex, the following conditions are equivalent to 
being a cograph:
1. 
can be constructed from isolated
vertices by graph disjoint unions and
graph join operations.
2. 
is a graph
disjoint union of connected distance-hereditary
graphs with graph diameter at most 2.
3. In every nonempty induced subgraph 
of 
, the intersection
of any maximal clique and any maximum
independent vertex set contains precisely one graph
vertex.
4. Every induced subgraph of 
with at least two vertices
has at least one pair of twin vertices.
5. The graph complement of every connected induced subgraph of 
with at least two vertices
is a disconnected graph.
6. Every connected induced subgraph of 
has graph diameter at most 2.
7. 
does not contain the path
graph 
as an induced subgraph.
The numbers of nonisomorphic cographs on 
, 2, ... vertices
are 1, 2, 4, 10, 24, 66, 180, 522, 1532, ... (OEIS A000084).
Brandstädt et al. (1999, definition 1.5) note that a graph
is a cograph iff its modular
decomposition tree contains only parallel and series
nodes. The counts of cographs on 
vertices are the same as the
counts of series-parallel networks with
indistinguishable edges,
as noted by Weisstein (2003ab). Enkosky (2011, p. 2) attributes a bijection
to Sloane. Here, multiple edges are allowed, and
interchanging parts connected in series or in parallel does not change the network
being counted (Finch 2003, pp. 2-3). The first cographs on 
to 5 vertices are illustrated
above. For 
, the number of cographs is always even.
The size of an induced cograph in a chordal graph can be much smaller than the vertex count of the
original graph. Hajebi (2026) proved that for every 
there is an 
-vertex interval graph whose
largest induced cograph has fewer than 
vertices. Together
with the lower bound 
for chordal graphs, this gives the sharp order 
, where 
is big-Theta notation
and 
is the floor
function.
