Sandwich Theorem

There are several theorems known as the "sandwich theorem."

In calculus, the squeeze theorem is also sometimes known as the sandwich theorem.

In graph theory, the sandwich theorem states that the Lovász number theta(G) of a graph G satisfies


where omega(G) is the clique number, chi(G) is the chromatic number of G, and G^_ is the graph complement of G. This can be rewritten by changing the role of graph complements, giving


which can be written using omega(G^_)=alpha(G) with alpha the independence number and theta(G)=chi(G^_) the clique covering number as


Furthermore, theta(G) can be computed efficiently despite the fact that the computation of the two numbers it lies between is an NP-hard problem.

See also

Fermat's Sandwich Theorem, Ham Sandwich Theorem, Lovász number, Shannon Capacity, Squeeze Theorem

Explore with Wolfram|Alpha


Grötschel, M.; Lovász, L.; and Schrijver, A. "The Ellipsoid Method and Its Consequences in Combinatorial Optimization." Combinatorica 1, 169-197, 1981.Knuth, D. E. "The Sandwich Theorem." Electronic J. Combinatorics 1, No. 1, A1, 1-48, 1994.

Referenced on Wolfram|Alpha

Sandwich Theorem

Cite this as:

Weisstein, Eric W. "Sandwich Theorem." From MathWorld--A Wolfram Web Resource.

Subject classifications