A Graph with 7 vertices each having degree 4 cannot be planar. Any hints on the proof?
A 4-Regular graph with 7 vertices is non planar
3 Answers
Show that the graph must contain a $K_{3,3}$ configuration.
Pick any pair of non-adjacent vertices, $v_1$ and $v_2$. Since $v_1$ and $v_2$ each have degree $4$ and there are only $5$ other vertices, they must have at least $3$ common neighbors.
Then, try to find a third vertex $v_3$ adjacent to the same common neighbors, thus constructing $K_{3,3}$.
Edit: Take $v_1$ and $v_2$ as described above. They must have at least $3$ common neighbors (and at most $4$). If they have $4$ common neighbors, then the remaining vertex shares the same $4$ neighbors as $v_1$ and $v_2$, so this forms a $K_{3,3}$ configuration.
So, say $v_1$ and $v_2$ share $v_3,v_4,v_5$ as common neighbors, with $v_1$ adjacent to $v_6$ and $v_2$ adjacent to $v_7$.
If $v_6$ and $v_7$ are not adjacent, then they each share $v_3,v_4,v_5$ as common neighbors with $v_1$ and $v_2$, giving a $K_{3,3}$ configuration.
If $v_6$ and $v_7$ are adjacent, then they are each adjacent to exactly two of $v_3,v_4,v_5$, and furthermore, they cannot be adjacent to the same pair. So say $v_6$ is adjacent to $v_3,v_4$ and $v_7$ is adjacent to $v_4,v_5$. Then, we have a $K_{3,3}$ configuration made of $v_1,v_2,v_6$ and $v_3,v_4,v_5$, where the 'edge' connecting $v_6$ to $v_5$ goes through $v_7$.
-
0Thank you. Could solve the question using your hint. – 2012-11-25
Up to isomorphism, there are two $4$-regular graphs on $7$ vertices, which can be exhaustively enumerated using geng
which comes with nauty. They are these two following graphs:
In the first graph, I highlighted a $K_{3,3}$ subgraph in orange (and thus it cannot be planar since $K_{3,3}$ is not planar).
In the second graph, I highlighted a $K_{2,3}$ subgraph in orange. We observe that by identifying the two blue vertices we obtain a vertex adjacent to all three red vertices, thereby giving a minor isomorphic to $K_{3,3}$ (we delete the unnecessary edges). Thus Wagner's Theorem implies this is also non-planar.
Instead of trying to find $4$-regular graphs on $7$ vertices, find complements of $4$-regular graphs on $7$ vertices. These are $2$-regular graphs, hence a $C_7$ and a $C_3 \cup C_4$.
In $C_7$ we can take vertices $(1,2,3)$ and $(4,5,6)$ in two partitions. Although $3$ and $4$ are connected, we will have a path between $3$ and $4$ via $7$ in $\overline{C_7}$ hence has a minor isomorphic to $K_{3,3}$.
In $C_3 \cup C_4$, we will take $(1,2,3)$ [from $C_3$] and $(4,5,6)$ [from $C_4$] in two partitions. So in $\overline{C_3 \cup C_4}$, we have a $K_{3,3}$ present.
Hence there are no planar $4$-regular graphs on $7$ vertices.
-
0A stronger challenge is to prove the non-existence of a $5$-regular planar graph on $14$ edges. – 2014-07-17