Question

(i) For which values of \(k\) is the \(k\)-cube \(Q_{k}\) planar? (ii) For which values of \(r, s\) and \(t\) is the complete tripartite graph \(K_{r, s t}\) planar?

Short answer

For the \(k\)-cube to be planar, \(k\) need to be less than or equal to 3. For the complete tripartite graph to be planar, the individual groups of vertices \(r, s, t\) each must not be greater than 2.

Step-by-step solution

Understand the concept of \(k\)-cube

A \(k\)-cube is a graph that has vertices representing the \(2^k\) corners of a \(k\)-dimensional cube. In general, a planar graph can only be achieved up to 3 dimensions. Any graph that represents a higher dimensional cube will not be planar.

Define \(k\) in terms of planar

From the information in Step 1, the \(k\)-cube will be planar where \(k \leq 3\). Beyond that, it ceases to be planar as higher-dimensional cubes cannot be drawn without intersections in our 2-D or 3-D plane.

Understand Complete Tripartite Graphs

A complete tripartite graph \(K_{r, s, t}\) is a graph with three distinct groups of vertices, with \(r\), \(s\), \(t\) vertices respectively, and each vertex is connected to every vertex not in its own group.

Define \(r, s, t\) in terms of Planar

The Kuratowski’s theorem states that a graph is planar if and only if it does not contain a subgraph homeomorphic to either \(K_5\) (complete graph on 5 vertices) or \(K_{3,3}\) (complete bipartite graph on 3, 3 vertices). Applying the same to tripartite graph, \(r,s,t\) each must be less than or equal to 2 for the graph to be planar because if any one of them becomes 3 the graph will be homeomorphic to \(K_{3,3}\), thus non-planar.

Key concepts

Understanding the k-cube

A **k-cube** represents a mathematical concept where a graph's vertices stand for the corners of a k-dimensional cube. The number of vertices is given by the formula \(2^k\). This makes the k-cube a fascinating structure as the number of dimensions increases. For instance, a 3-cube is a familiar 3D cube in typical geometry.
For a graph to be planar, it must be drawable on a two-dimensional plane without any of its edges crossing. In the case of k-cubes, these are planar only up to three dimensions. Beyond a 3-cube, it is impossible to represent the cube without edge intersections in a plane. Therefore, for a k-cube to remain planar, \(k\) must satisfy \(k \leq 3\).
When applying these rules to higher dimensions, such as a 4-cube, it becomes a challenge to visualize because these graphs cannot be represented without edge overlaps, confirming their non-planarity.

Understanding Complete Tripartite Graphs

A **complete tripartite graph**, represented as \(K_{r, s, t}\), is a graph that consists of three sets of vertices. Each set has a designated number of vertices: \(r\), \(s\), and \(t\), respectively. The important thing about this type of graph is that every vertex in one group connects to all vertices in the other two groups but not to vertices within its own group.
This interlinking results in a complete connectivity among the three groups, making these graphs interesting to study in terms of planarity. To determine if \(K_{r, s, t}\) is planar, we refer to **Kuratowski’s theorem**. This theorem tells us the graph is non-planar if it contains subdivisions of \(K_5\) or \(K_{3,3}\) within it.
For \(K_{r, s, t}\) to remain planar, \(r\), \(s\), and \(t\) must all be less than or equal to 2. Expanding any of these values to 3 and beyond results in a structure similar to \(K_{3,3}\), making the graph non-planar, as it could not be depicted without edge crossings on a flat surface.

Exploring Kuratowski’s Theorem

**Kuratowski’s theorem** is pivotal in the study of graph planarity. It provides a simple criterion: a graph is planar if and only if it does not contain a subgraph that is homeomorphic to \(K_5\) or \(K_{3,3}\). Understanding these underlying subgraphs helps when analyzing or determining the planarity of more complex graphs.
Subgraphs homeomorphic to \(K_5\), the complete graph on five vertices, or \(K_{3,3}\), the complete bipartite graph, become the basis for categorizing non-planar graphs. If such a substructure is found as a part of a larger graph, planarity is immediately ruled out.

• **\(K_5\):** Any graph having a subdivision containing all points interconnected (like a five-sided polygon) is non-planar.
• **\(K_{3,3\):** A graph resembling two sets of three interlinked vertices, where vertices of one set are connected to all vertices of the other set, is also non-planar.

This theorem provides a strong foundation and simplifies the otherwise complex problem of graph planarity by focusing on these two non-planar configurations.