Suppose there are three cottages that each need to be connected to the gas, water, and electric companies. Is there a way to do so without any of the lines crossing each other?

In more formal terms, this asks whether the complete bipartite graph K_{3,3} is planar. Kazimierz Kuratowski proved in 1930 that K_{3,3} is nonplanar, and thus that the three cottage problem has no solution.

One of the most famous and productive problems of graph theory is the four color problem: "Is it true that any map drawn in the plane may have its regions colored with four colors, in such a way that any two regions having a common border have different colors?".

This problem was first posed by Francis Guthrie in 1852 and the first written record of this problem is a letter of De Morgan addressed to Hamilton the same year.

Covering problems are specific instances of subgraph-finding problems, and they tend to be closely related to the clique problem or the independent set problem.

Share your thoughts, questions and commentary here

Want to know more? Search encyclopedia, statistics and forums:

Press Releases |
Feeds |
Contact
The Wikipedia article included on this page is licensed under the
GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m