Question

Three unfriendly neighbours use the same water, oil and treacle wells. In order to avoid meeting, they wish to build non-crossing paths from each of their houses to each of the three wells. Can this be done?

Short answer

No, it's not possible for the three unfriendly neighbours to construct non-crossing paths to each of the three wells. Kuratowski's Theorem proves that a \(K_{3,3}\) graph is non-planar, thus there isn't a way for the paths between the houses and wells to be drawn without crossing.

Step-by-step solution

Understanding the Problem

Firstly, recognize that the problem involves three neighbours (nodes or vertices) each needing to connect to three resources (wells or other nodes). They do not want their paths to cross which implies a solution must be found for a planar graph.

Graph Representation

Secondly, create a graph where the houses and wells form part of the graph and the paths between them are edges. This kind of graph is known as a complete bipartite graph, represented as \(K_{3,3}\).

Application of Kuratowski's theorem

Lastly, apply Kuratowski's theorem. Which states that a graph is planar (can be drawn on a plane without crossing edges) if and only if it does not contain a subgraph that is isomorphic to \(K_{3,3}\) (or the complete graph \(K_5\)). This means that the graph of our problem \(K_{3,3}\) is inherently non-planar, so it's impossible to create non-crossing paths for this graph.

Key concepts

Kuratowski's Theorem

Kuratowski's theorem is a fundamental result in the field of graph theory that provides a crucial criterion for determining whether a given graph is planar or not. A planar graph is one that can be drawn on a two-dimensional plane without any of its edges crossing each other.

Kazimierz Kuratowski, a Polish mathematician, established in 1930 that a graph is non-planar if and only if it contains a subgraph that can be transformed into one of the two specific graphs: the complete graph with five vertices, denoted as \(K_5\), or the complete bipartite graph with six vertices split into two sets of three, denoted as \(K_{3,3}\). These particular graphs are called Kuratowski graphs.

Understanding this theorem is pivotal as it allows us to immediately identify non-planar graphs if they are able to host one of these Kuratowski graphs. In the given exercise, the impossibility of creating non-crossing paths stems precisely from this theorem as it exposes the inherent non-planarity of the \(K_{3,3}\) graph formed by the houses and the wells.

Complete Bipartite Graph

A complete bipartite graph is a special type of graph in graph theory. It is defined as a set of vertices split into two distinct non-overlapping sets such that every vertex in the first set is connected to every vertex in the second set, and there are no edges within each individual set.

The complete bipartite graph is denoted as \(K_{m,n}\), where \(m\) and \(n\) are the number of vertices in two respective sets. For example, the complete bipartite graph \(K_{3,3}\) means there are two sets of vertices with three vertices in each, and each vertex from one set connects to every vertex in the other set.

This particular type of graph is significant in our exercise because the graph representing the houses and wells is a complete bipartite graph, which is part of why the problem does not have a solution; \(K_{3,3}\) cannot be drawn without edges crossing due to its non-planar nature.

Graph Theory

Graph theory is a fascinating and fundamental area of mathematics that studies the properties of graphs, which are mathematical structures used to model pairwise relations between objects. A graph consists of vertices (or nodes) and edges (or lines) that connect pairs of vertices.

In the context of the problem given, the houses and the wells can be considered as vertices, and the paths that connect them are modeled as edges. Graph theory provides us with tools to answer various real-world problems by abstracting them into vertices and edges, then applying theorems like Kuratowski's to analyze their properties.

Graph theory is not only about planar graphs but also extends to various types such as bipartite graphs, directed graphs, weighted graphs, and many more, each serving a particular purpose and having its own set of unique properties and applications.

Non-Planar Graph

A non-planar graph is one that cannot be drawn on a plane without some edges crossing. The classic examples provided by Kuratowski's theorem are \(K_5\) and \(K_{3,3}\). The presence of such a graph within another graph is a clear indication of its non-planarity.

This is particularly relevant to the exercise because the problem actually constructs a \(K_{3,3}\) scenario, which is inherently non-planar. Recognizing a graph's non-planarity is crucial in fields such as circuit board design or road planning, where overlap is either unacceptable or highly undesired.

In our educational setting, understanding non-planar graphs helps in visualizing the complexities of graph drawing and the limitations of arranging vertices and edges in a plane, emphasizing the creative and analytical processes involved in problem-solving within graph theory.