In graph theory, a highly irregular graph is a graph in which, for every vertex, all neighbors of that vertex have distinct degrees. History Irregular graphs were initially characterized by Yousef Alavi, Gary Chartrand, Fan Chung, Paul Erdős, Ronald Graham, and Ortrud Oellermann. They were motivated to define the ‘opposite’ of a regular graph, a concept which has been thoroughly studied and well understood. Locality and regularity Defining an ‘irregular graph’ was not immediately obvious. In a k-regular graph, all vertices have degree k. In any graph G with more than one vertex, two vertices in G must have the same degree, so an irregular graph cannot be defined as a graph with all vertices of different degrees. One may be tempted then to define an irregular graph as having all vertices of distinct degrees except for two, but these types of graphs are also well understood and thus not interesting. Graph theorists thus turned to the issue of local regularity. A graph is locally regular at a vertex v if all vertices adjacent to v have degree r. A graph is thus locally irregular if for each vertex v of G the neighbors of v have distinct degrees, and these graphs are thus termed highly irregular graphs. Properties of irregular graphs Some facts about highly irregular graphs outlined by Alavi et al.: If v is a vertex of maximum degree d in a highly irregular graph H, then v is adjacent to exactly one vertex of degree 1, 2, ..., d. The largest degree in a highly irregular graph is at most half the number of vertices. If H is a highly irregular graph with maximum degree d, one can construct a highly irregular graph of degree d+1 by taking two copies of H and adding an edge between the two vertices of degree d. H(n)/G(n) goes to 0 as n goes to infinity exponentially rapidly, where H(n) is the number of (non-isomorphic) highly irregular graphs with n vertices, and G(n) is the total number of graphs with n vertices. For every graph G, there exists a highly irregular graph H containing G as an induced subgraph. This last observation can be considered analogous to a result of Dénes Kőnig, which states that if H is a graph with greatest degree r, then there is a graph G which is r-regular and contains H as an induced subgraph. Applications