This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A004401 Least number of edges in graph containing all trees on n nodes.
(Formerly M0989)
0, 1, 2, 4, 6, 8, 11, 13, 16, 18 (list; graph; refs; listen; history; text; internal format)



Paul Tabatabai's program only tests graphs on n nodes, but the term a(9) = 16 is now confirmed. It seems to be sufficient to test only graphs on n vertices (cf. Related Questions, Question 1 in Chung, Graham, and Pippenger). Moreover, if this assumption is true, then the next terms are a(11) = 22 and a(12) = 24. Also note that my program can be used to enumerate all possible solutions. - Manfred Scheucher, Jan 25 2018


R. L. Graham, personal communication.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


Table of n, a(n) for n=1..10.

F. R. K. Chung, R. L. Graham, On graphs which contain all small trees, J. Combinatorial Theory Ser. B 24 (1978), no. 1, 14--23. MR0505812 (58 #21808a)

F. R. K. Chung, R. L. Graham, N. Pippenger, On graphs which contain all small trees. II. Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, pp. 213-223. Colloq. Math. Soc. Janos Bolyai, 18. North-Holland, Amsterdam, 1978.

Manfred Scheucher, Sage Program

Manfred Scheucher, Graph on 10 vertices and 18 edges containing all trees on 10 vertices.

Paul Tabatabai, Exhaustive search proving a(9) = 16. (Sage script)

Paul Tabatabai, Graph on 9 vertices and 16 edges containing all trees on 9 vertices.

Index entries for sequences related to trees


Cf. A212555.

Sequence in context: A193766 A262773 A186152 * A022819 A081527 A070978

Adjacent sequences:  A004398 A004399 A004400 * A004402 A004403 A004404




N. J. A. Sloane, R. K. Guy


a(9) by Paul Tabatabai, Jul 17 2016

a(10) by Manfred Scheucher, Jan 25 2018



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 25 01:44 EDT 2018. Contains 301219 sequences. (Running on oeis4.)