4 ms·
For every set of two vertices, there is at least one path that connects them.
by IncreasePosts 2y ago
For every set of two vertices, there is at least one path that connects them.
- n4r9 2y agoBut... That's not part of the definition of Ramsey numbers. Often it's defined in terms of a complete graph where the egdmmdges are coloured either red or blue. But there's nothing about the blue subgraph or red subgraph needing to be connected. https://en.m.wikipedia.org/wiki/Ramsey%27s_theorem https://en.m.wikipedia.org/wiki/Ramsey%27s_theorem
- TheRealPomax 2y agoScroll down a bit to https://en.m.wikipedia.org/wiki/Ramsey%27s_theorem#Ramsey_numbers https://en.m.wikipedia.org/wiki/Ramsey%27s_theorem#Ramsey_nu.... Ramsey numbers arise from the original problem, and play a role in its proof, but they are not "the same thing" as Ramsey's Theorem.
- n4r9 2y agoSure, Ramsey's Theorem guarantees that Ramsey numbers exist. But at no point is it assumed that the graph is connected. The section you linked puts it quite simply: > The Ramsey number is the minimum number of vertices, v = R(m, n), such that all undirected simple graphs of order v, contain a clique of order m, or an independent set of order n. The graph is undirected and simple. But it need not be connected.