Intrinsically Linked Graph
An intrinsically linked graph is a graph having the property that any embedding of it in three dimensions contains a nontrivial link. A graph is intrinsically linked iff it contains one of the seven Petersen family graphs (Robertson et al. 1993) as a graph minor.
The complete graph K_6 (left) is intrinsically linked because it contains at least two linked triangles. The complete k-partite graph K_(3,3,1) (right) is also intrinsically linked.
A graph that is not intrinsically linked is said to be a linklessly embeddable graph.
A graph on n>6 nodes with edge count m>10n-6 is intrinsically linked.
See also
Complete Graph, Complete k-Partite Graph, Linklessly Embeddable Graph, Petersen Family GraphsExplore with Wolfram|Alpha
References
Adams, C. C. The Knot Book: An Elementary Introduction to the Mathematical Theory of Knots. New York: W. H. Freeman, pp. 217-221, 1994.Naimi, R.; Pavelescu, A.; and Pavelescu, E. "New Bounds of Maximal Linkless Graphs." 20 Sep 2020. https://arxiv.org/abs/2007.10522.Odeneal, Y.; Naimi, R.; Pavelescu, A.; and Pavelescu, E. "The Complement Problem for Linklessly Embeddable Graphs." J. Knot Theory and Its Ramifications 2250075, 1-10, 2022.Robertson, N.; Seymour, P. D.; and Thomas, R. "Linkless Embeddings of Graphs in 3-Space." Bull. Amer. Math. Soc. 28, 84-89, 1993.Referenced on Wolfram|Alpha
Intrinsically Linked GraphCite this as:
Weisstein, Eric W. "Intrinsically Linked Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/IntrinsicallyLinkedGraph.html