R. Merris, Antiregular graphs are universal for trees, Publ. Elektrotehn. Fak. Univ. Beograd Ser. Mat. 14 (2003), 1-3.

Graph G on n vertices is antiregular if G = K1 or if the vertex degrees of G attain n-1 different values. For n > 1, there are (up to isomorphism) exactly two antiregular graphs on n vertices, one connected and the other disconnected, and these two are complementary. Denote by An the unique connected antiregular graph on n vertices. The main result of this note is that every tree on n vertices is isomorphic to a subgraph of An.

Antiregular graphs have many other interesting properties, some of which are mentioned in the note. For example, An has degree sequence

(n-1,n-2, ... , n-r+1, n-r, n-r, n-r-1, ... ,2,1),

where r = [(n+1)/2] (the greatest integer function); An is a threshold graph, hence chordal, hence perfect; its line graph is hamiltonian; it has bipartite character; its Laplacian spectrum consists of all but one of the integers 0, 1, 2, ... , n (the "missing" eigenvalue is [(n+1)/2]); with s = [n/2], the chromatic polynomial of An is

x([x-1][x-2]...[x-s])^2, if n is odd, and

x([x-1][x-2]...[x-s+1])^2[x-s], if n is even;

in particular, the chromatic number of An is [n/2] + 1; finally, the number, q(n,k), of k-matchings of An satisfies q(n,0) = 1 (by convention) and, for k > 0 and n > 3,

q(n,k) = q(n-2,k) + (n-2k+1)q(n-2,k-1).

Unfortunately, the published version of the note contains an omission and two misprints: (1) The dedication to the memory of Helen Frances Turnage Diehl was omitted. (2) An edge is missing from the illustration of A5 in Figure 1. (3) The author's correct URL is

http://www.sci.csuhayward.edu/~rmerris