# Universal graph

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Universal_graph
> Markdown URL: https://mediated.wiki/source/Universal_graph.md
> Source: https://en.wikipedia.org/wiki/Universal_graph
> Source revision: 1329298404
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [mathematics](/source/Mathematics), a **universal graph** is an infinite [graph](/source/Graph_(discrete_mathematics)) that contains *every* finite (or at-most-[countable](/source/Countable)) graph as an induced [subgraph](/source/Glossary_of_graph_theory#Subgraphs). A universal graph of this type was first constructed by [Richard Rado](/source/Richard_Rado)[1][2] and is now called the [Rado graph](/source/Rado_graph) or random graph. More recent work[3] [4] has focused on universal graphs for a graph family F: that is, an infinite graph belonging to F that contains all finite graphs in F. For instance, the [Henson graphs](/source/Henson_graph) are universal in this sense for the i-clique-free graphs.

An infinite path is a universal graph for the family of path graphs.

A universal graph for a family F of graphs can also refer to a member of a sequence of finite graphs that contains all graphs in F; for instance, every finite tree is a subgraph of a sufficiently large [hypercube graph](/source/Hypercube_graph)[5] so a hypercube can be said to be a universal graph for trees. However it is not the smallest such graph: it is known that there is a universal graph for n-vertex trees, with only n vertices and O(*n* log *n*) edges, and that this is optimal.[6] A construction based on the [planar separator theorem](/source/Planar_separator_theorem) can be used to show that n-vertex [planar graphs](/source/Planar_graph) have universal graphs with O(*n*3/2) edges, and that bounded-degree planar graphs have universal graphs with O(*n* log *n*) edges.[7][8][9] It is also possible to construct universal graphs for planar graphs that have *n*1+*o*(1) vertices.[10] [Sumner's conjecture](/source/Sumner's_conjecture) states that [tournaments](/source/Tournament_(graph_theory)) are universal for [polytrees](/source/Polytree), in the sense that every tournament with 2*n* − 2 vertices contains every polytree with n vertices as a subgraph.[11]

A family F of graphs has a universal graph of polynomial size, containing every n-vertex graph as an [induced subgraph](/source/Induced_subgraph), if and only if it has an [adjacency labelling scheme](/source/Implicit_graph) in which vertices may be labeled by *O*(log *n*)-bit bitstrings such that an algorithm can determine whether two vertices are adjacent by examining their labels. For, if a universal graph of this type exists, the vertices of any graph in F may be labeled by the identities of the corresponding vertices in the universal graph, and conversely if a labeling scheme exists then a universal graph may be constructed having a vertex for every possible label.[12]

In older mathematical terminology, the phrase "universal graph" was sometimes used to denote a [complete graph](/source/Complete_graph).

The notion of universal graph has been adapted and used for solving mean payoff games.[13]

## References

1. **[^](#cite_ref-1)** [Rado, R.](/source/Richard_Rado) (1964). ["Universal graphs and universal functions"](https://doi.org/10.4064%2Faa-9-4-331-340). *Acta Arithmetica*. **9** (4): 331–340. [doi](/source/Doi_(identifier)):[10.4064/aa-9-4-331-340](https://doi.org/10.4064%2Faa-9-4-331-340). [MR](/source/MR_(identifier)) [0172268](https://mathscinet.ams.org/mathscinet-getitem?mr=0172268).

1. **[^](#cite_ref-2)** [Rado, R.](/source/Richard_Rado) (1967). "Universal graphs". *A Seminar in Graph Theory*. Holt, Rinehart, and Winston. pp. 83–85. [MR](/source/MR_(identifier)) [0214507](https://mathscinet.ams.org/mathscinet-getitem?mr=0214507).

1. **[^](#cite_ref-3)** Goldstern, Martin; Kojman, Menachem (1996). ["Universal arrow-free graphs"](https://doi.org/10.1007%2FBF00052907). *[Acta Mathematica Hungarica](/source/Acta_Mathematica_Hungarica)*. **1973** (4): 319–326. [arXiv](/source/ArXiv_(identifier)):[math.LO/9409206](https://arxiv.org/abs/math.LO/9409206). [doi](/source/Doi_(identifier)):[10.1007/BF00052907](https://doi.org/10.1007%2FBF00052907). [MR](/source/MR_(identifier)) [1428038](https://mathscinet.ams.org/mathscinet-getitem?mr=1428038).

1. **[^](#cite_ref-4)** Cherlin, Greg; [Shelah, Saharon](/source/Saharon_Shelah); Shi, Niandong (1999). "Universal graphs with forbidden subgraphs and algebraic closure". *Advances in Applied Mathematics*. **22** (4): 454–491. [arXiv](/source/ArXiv_(identifier)):[math.LO/9809202](https://arxiv.org/abs/math.LO/9809202). [doi](/source/Doi_(identifier)):[10.1006/aama.1998.0641](https://doi.org/10.1006%2Faama.1998.0641). [MR](/source/MR_(identifier)) [1683298](https://mathscinet.ams.org/mathscinet-getitem?mr=1683298). [S2CID](/source/S2CID_(identifier)) [17529604](https://api.semanticscholar.org/CorpusID:17529604).

1. **[^](#cite_ref-5)** Wu, A. Y. (1985). "Embedding of tree networks into hypercubes". *Journal of Parallel and Distributed Computing*. **2** (3): 238–249. [doi](/source/Doi_(identifier)):[10.1016/0743-7315(85)90026-7](https://doi.org/10.1016%2F0743-7315%2885%2990026-7).

1. **[^](#cite_ref-6)** [Chung, F. R. K.](/source/Fan_Chung); [Graham, R. L.](/source/Ronald_Graham) (1983). ["On universal graphs for spanning trees"](https://www.math.ucsd.edu/~fan/mypaps/fanpap/35universal.pdf) (PDF). *Journal of the London Mathematical Society*. **27** (2): 203–211. [CiteSeerX](/source/CiteSeerX_(identifier)) [10.1.1.108.3415](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.108.3415). [doi](/source/Doi_(identifier)):[10.1112/jlms/s2-27.2.203](https://doi.org/10.1112%2Fjlms%2Fs2-27.2.203). [MR](/source/MR_(identifier)) [0692525](https://mathscinet.ams.org/mathscinet-getitem?mr=0692525)..

1. **[^](#cite_ref-7)** [Babai, L.](/source/L%C3%A1szl%C3%B3_Babai); [Chung, F. R. K.](/source/Fan_Chung); [Erdős, P.](/source/Paul_Erd%C5%91s); [Graham, R. L.](/source/Ronald_Graham); [Spencer, J. H.](/source/Joel_Spencer) (1982). "On graphs which contain all sparse graphs". In Rosa, Alexander; Sabidussi, Gert; Turgeon, Jean (eds.). [*Theory and practice of combinatorics: a collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday*](https://renyi.hu/~p_erdos/1982-12.pdf) (PDF). Annals of Discrete Mathematics. Vol. 12. pp. 21–26. [MR](/source/MR_(identifier)) [0806964](https://mathscinet.ams.org/mathscinet-getitem?mr=0806964).

1. **[^](#cite_ref-8)** Bhatt, Sandeep N.; [Chung, Fan R. K.](/source/Fan_Chung); [Leighton, F. T.](/source/F._Thomson_Leighton); [Rosenberg, Arnold L.](/source/Arnold_L._Rosenberg) (1989). "Universal graphs for bounded-degree trees and planar graphs". *[SIAM Journal on Discrete Mathematics](/source/SIAM_Journal_on_Discrete_Mathematics)*. **2** (2): 145–155. [doi](/source/Doi_(identifier)):[10.1137/0402014](https://doi.org/10.1137%2F0402014). [MR](/source/MR_(identifier)) [0990447](https://mathscinet.ams.org/mathscinet-getitem?mr=0990447).

1. **[^](#cite_ref-9)** [Chung, Fan R. K.](/source/Fan_Chung) (1990). "Separator theorems and their applications". In [Korte, Bernhard](/source/Bernhard_Korte); [Lovász, László](/source/L%C3%A1szl%C3%B3_Lov%C3%A1sz); Prömel, Hans Jürgen; et al. (eds.). [*Paths, Flows, and VLSI-Layout*](https://archive.org/details/pathsflowsvlsila0000unse/page/17). Algorithms and Combinatorics. Vol. 9. Springer-Verlag. pp. [17–34](https://archive.org/details/pathsflowsvlsila0000unse/page/17). [ISBN](/source/ISBN_(identifier)) [978-0-387-52685-0](https://en.wikipedia.org/wiki/Special:BookSources/978-0-387-52685-0). [MR](/source/MR_(identifier)) [1083375](https://mathscinet.ams.org/mathscinet-getitem?mr=1083375).

1. **[^](#cite_ref-10)** Dujmović, Vida; Esperet, Louis; Joret, Gwenaël; Gavoille, Cyril; Micek, Piotr; Morin, Pat (2021), "Adjacency Labelling for Planar Graphs (And Beyond)", *Journal of the ACM*, **68** (6): 1–33, [arXiv](/source/ArXiv_(identifier)):[2003.04280](https://arxiv.org/abs/2003.04280), [doi](/source/Doi_(identifier)):[10.1145/3477542](https://doi.org/10.1145%2F3477542)

1. **[^](#cite_ref-11)** [Sumner's Universal Tournament Conjecture](http://www.math.uiuc.edu/~west/openp/univtourn.html), Douglas B. West, retrieved 2010-09-17.

1. **[^](#cite_ref-12)** Kannan, Sampath; [Naor, Moni](/source/Moni_Naor); [Rudich, Steven](/source/Steven_Rudich) (1992), "Implicit representation of graphs", *[SIAM Journal on Discrete Mathematics](/source/SIAM_Journal_on_Discrete_Mathematics)*, **5** (4): 596–603, [doi](/source/Doi_(identifier)):[10.1137/0405049](https://doi.org/10.1137%2F0405049), [MR](/source/MR_(identifier)) [1186827](https://mathscinet.ams.org/mathscinet-getitem?mr=1186827).

1. **[^](#cite_ref-13)** Czerwiński, Wojciech; Daviaud, Laure; Fijalkow, Nathanaël; Jurdziński, Marcin; Lazić, Ranko; Parys, Paweł (2018-07-27). "Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games". *Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms*. pp. 2333–2349. [arXiv](/source/ArXiv_(identifier)):[1807.10546](https://arxiv.org/abs/1807.10546). [doi](/source/Doi_(identifier)):[10.1137/1.9781611975482.142](https://doi.org/10.1137%2F1.9781611975482.142). [ISBN](/source/ISBN_(identifier)) [978-1-61197-548-2](https://en.wikipedia.org/wiki/Special:BookSources/978-1-61197-548-2). [S2CID](/source/S2CID_(identifier)) [51865783](https://api.semanticscholar.org/CorpusID:51865783).

## External links

- [The panarborial formula](https://www.theoremoftheday.org/CombinatorialTheory/Panarboreal/TotDPanarboreal.pdf), "Theorem of the Day" concerning universal graphs for trees

---
Adapted from the Wikipedia article [Universal graph](https://en.wikipedia.org/wiki/Universal_graph) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Universal_graph?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.