Für einen vollständigen Graphen mit gerader Anzahl von Knoten und positiven Gewichten , der die Dreiecksungleichung erfüllt, sei die minimale Kosten-perfekte Paarung und die minimale Kosten-Reise des Handlungsreisenden. Dann ist .

Es gibt einen Algorithmus in polynomieller Zeit, der eine -Approximation für das metrische Problem des Handlungsreisenden findet.

Jeder Graph ohne Dreieck hat eine chromatische Zahl von höchstens 100.

Jeder Zyklus hat eine korrekte 2-Farbgebung.

Wenn ein bipartiter Graph ist und in ein Matching aufweist, das nicht kardinalitätsmaximal ist, dann gibt es in einen augmentierenden Pfad bezüglich .

Wenn ein zusammenhängender Graph mit einem maximalen Grad von 100 ist, dann hat eine korrekte Einfärbung in 100 Farben, es sei denn, ist ein vollständiger Graph.

Wenn ein Graph mit maximalem Grad ist, findet ein Greedy-Algorithmus immer die richtige Einfärbung in höchstens Farben.

Es gibt einen effizienten Algorithmus, der für jeden planaren Graphen eine geeignete Einfärbung in 6 Farben findet.

Das (kardinalitäts-)maximale Matching in einem bipartiten Graphen kann in der Zeit gefunden werden.

Jeder -reguläre bipartite Graph für hat ein Matching der Größe .