A highly irregular graph is a connected graph for which the vertices adjacent to each vertex have distinct vertex degrees. Highly irregular graphs exist on all orders except 3, 5 and 7, with the numbers of such graphs on 1, 2, ... nodes given by 1, 1, 0, 1, 0, 1, 0, 3, 3, 13, 21, 110, 474, 2545, ... (OEIS A217246).
Small examples are illustrated above with the vertex degree of each node labeled and summarized in the following table.
| vertex count | highly irregular graphs |
| 1 | singleton graph |
| 2 | path graph  |
| 4 | path graph  |
| 6 | A graph |
| 8 | 4-centipede graph |
Larger examples on 
and 9 nodes are illustrated
above, again with the vertex degree of each node
labeled.
Highly irregular graphs are apex and nonhamiltonian. Those with more than one vertex are bridged.
If 
is a vertex with maximum
vertex degree 
in a highly irregular graph, then 
is adjacent to exactly one vertex
of degree 1, 2, ..., 
(Alavi et al. 1987).
The maximum vertex degree in a highly irregular graph on 
vertices is at most 
, where 
is the floor function
(Alavi et al. 1987).
