Question

Let \(G\) be a simple graph with at least 11 vertices, and let \(\bar{G}\) be its complement. (i) Prove that \(G\) and \(\bar{G}\) cannot both be planar. (In fact, a similar result holds if 11 is replaced by 9 , though this is difficult to prove.) (ii) Find a graph \(G\) with eight vertices for which \(G\) and \(\bar{G}\) are both planar.

Short answer

Based on the application of Euler's formula and the derivation of a contradiction, both a simple graph \(G\) and its complement \(\bar{G}\) can't be planar when the graph has at least 11 vertices. However, a graph with 8 vertices, where each vertex has degree 2 and forms a cycle, can be planar along with its complement.

Step-by-step solution

Analyze & Define Planar Graphs

A planar graph is one which can be drawn on a plane in such a way that no edges intersect each other. The simple graph \(G\) and its complement \(\bar{G}\) are planar if, and only if, they can both be drawn in the plane without crossing edges.

Formulate Euler's relation and List Assumptions

Euler's formula states that for any simple, connected, planar graph: \(V - E + F = 2\), where \(V\) = vertices, \(E\) = edges and \(F\) = faces. Let's presume, initially, both \(G\) and \(\bar{G}\) are planar. Then for a graph G with n vertices and e edges, the formula suggests \(n-e+f=2\). And for its complement graph, \(\bar{G}\), it has the same vertices, \(n\), but edges are all the possible combinations of two vertices minus the edges in \(G\), which are \(\frac{n(n-1)}{2}-e\), and the faces are \(\bar{f}\). Hence for \(\bar{G}\), the formula implies \(n - (\frac{n(n-1)}{2} - e) + \bar{f} = 2\).

Derive Contradiction for Part (i)

By adding up these two equations from step 2, and using the fact that the total faces in the plane \(f+\bar{f}\) is equal to \(n+1\), we get; \(2n + 1 = n + \frac{n(n-1)}{2} + 2\). Simplifying further, we get; \(\frac{n(n-1)}{2} 11+1\). Hence, we just proved that both \(G\) and its complement \(\bar{G}\) cannot be planar when the graph consists of at least 11 vertices.

Find Planar Graph for Part (ii)

For Part (ii), one of the simplest solutions is to find a graph G with 8 vertices where every vertex has degree 2 such that it forms a cycle graph (the vertices form a circle). Since all vertices have degree 2 and the graph is cyclic, the graph \(G\) is planar. Now, the graph \(\bar{G}\), the complement of \(G\), will be represented by joining all vertices that are not already joined by an edge and no three vertices are joined in a loop, so no crossing edges. Therefore, \(\bar{G}\) is planar.

Key concepts

Euler's Formula

One of the foundational concepts in graph theory is Euler's formula, which is a remarkable characteristic of planar graphs. Planar graphs are those that can be drawn on a plane without any edges crossing. Euler's formula provides a relationship between the number of vertices (\textbf{V}), edges (\textbf{E}), and faces (\textbf{F}) of a connected, planar graph:

\[ V - E + F = 2 \]
This elegant equation is the bedrock for proving various properties of planar graphs. For example, in the exercise, Euler's formula is pivotal in demonstrating that a simple graph with at least 11 vertices and its complement cannot both be planar. This is because when you apply Euler's formula to both the graph and its complement, you’re led to a contradiction if both graphs were considered planar. Educational tip: Remember that in order for Euler's formula to hold, the graph must be simple, connected, and planar. If any of these conditions are not met, the formula does not apply.
When understanding or proving concepts with Euler's formula, visualizing or drawing graphs can be particularly helpful. Break down each component of the formula and reflect on how changes in \textbf{V}, \textbf{E}, or \textbf{F} affect the others. This visualization can greatly aid students in grasping the relationship that Euler's formula describes.

Graph Complement

The graph complement is another intriguing concept in graph theory. Given a simple graph \textbf{G}, its complement, denoted as \textbf{\(\bar{G}\)}, is a graph on the same set of vertices where two distinct vertices are adjacent in \textbf{\(\bar{G}\)} if and only if they are not adjacent in \textbf{G}. In the context of planar graphs, it's interesting to examine whether a graph and its complement can both be planar.

In general, the complement of a dense graph (with many edges) is likely to be sparse (with fewer edges), and vice versa. For beginner learners, an easy way to visualize a graph complement is to take a simple graph and literally draw the 'missing' edges – the ones that are absent in the original graph. Exercise caution, though! As the exercise points out, once you reach a certain number of vertices (in this case, 11 or more), a simple graph and its complement can't both be planar due to the constraints imposed by the number of edges and the resulting need for some edges to cross in at least one of the graphs, leading to the contradiction showcased when applying Euler's formula.

Simple Graph

Lastly, let's talk about the simple graph. A simple graph is a type of graph where there is at most one edge between any two vertices, and there are no loops (edges connected to the same vertex). These restrictions make simple graphs a fundamental structure within graph theory. They’re an ideal starting point when studying the properties and characteristics of different kinds of graphs, including planar graphs.

When dealing with simple graphs, it's essential to note that they are the underlying structure when considering planar graphs and their complements, as seen in the exercise solution. The attributes of a simple graph facilitate the application of Euler's formula, which is based on the premise of no duplicate edges and no loops. For students, remember that constructing a simple graph is about connecting different vertices with unique edges; imagine dot-to-dot drawings where each dot can only be connected to another with a single, straight line.
Visual aids, such as drawing small simple graphs, help in learning these concepts; as part of the exercise advice, start with basic examples and gradually increase complexity. This stepwise approach is particularly effective for grasping the essence of simple graphs and exploring their properties, such as planarity and the potential for a graph to have a planar complement.