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 nonisomorphic highly irregular 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 nonhamiltonian. Those with more than one vertex are bridged.
Every simple graph of graph order 
is an induced subgraph of a highly irregular
graph of graph order 
(Alavi et al. 1987, p. 238). In particular,
the construction for the complete graph 
gives a highly irregular graph on 20 vertices
that is not apex.
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, p. 236).
The maximum vertex degree in a highly irregular graph on 
vertices is at most 
, where 
is the floor function
(Alavi et al. 1987, p. 236).
A graph Cartesian product 
of path
graphs with 
is highly irregular iff all but at most one factor are singleton graphs and any remaining path
graph has graph order 2 or 4. Indeed, every highly
irregular graph with an edge has a vertex
of degree one by the maximum
vertex degree property above. The minimum
vertex degree of such a graph Cartesian
product is the number of factors with graph order
greater than one, so at most one factor can be nontrivial. The path
graph 
has two neighbors of degree
one at its middle vertex, while 
for 
has a vertex with two
neighbors of degree
two. The path graphs 
, 
, and 
satisfy the definition.
