Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A Graph with 7 vertices each having degree 4 cannot be planar. Any hints on the proof?

share|improve this question

3 Answers 3

up vote 4 down vote accepted

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$.

share|improve this answer
    
Thank you. Could solve the question using your hint. –  rTeja Nov 25 '12 at 9:12

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:

The two 4-regular graphs on 7 vertices

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.

share|improve this answer

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.

share|improve this answer
    
A stronger challenge is to prove the non-existence of a $5$-regular planar graph on $14$ edges. –  Uma kant Jul 17 at 3:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.