Nonexistence of universal graphs without some trees (Q1385982)

If \({\mathcal H}\) is a class of graphs then \(X\in {\mathcal H}\) is universal if every \(Y\in {\mathcal H}\) embeds into \(X\). The main result of this paper states that for \(r\geq 3\), if \(T\) is a finite tree with two neighbouring vertices of degree \(r+1\), \(1\), respectively, and of degree \(\leq r\) for the other vertices, then there is no universal, countable, \(T\)-free graph. This theorem is proved by a sequence of lemmata which are interesting on their own, too. For instance, it is shown, that for \(r\geq 3\) there exist \(r\)-regular, \(r\)-connected graphs with arbitrarily large girth. Some statements are deduced from properties of random regular graphs.