MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider a connected graph whose cycles have length at least 4, the maximum valence is 4, there are 2 vertices of valence 2 and 4 of valence 3. I would like to show graphs of this type are planar . I am not sure whether the result is true or not. I am essentially trying to show that any connected subgraph whose vertices have at least valence 2 satisfy $2V -4 \geq E$. You may also note that the two vertices of valence 2 are not connected by a single edge, in fact the two vertices are antipodal points of a 4 cycle.

share|cite|improve this question
up vote 4 down vote accepted

With the information given, you can not guarantee planarity. One counter example would be a graph consisting of the complete bipartite graph $K_{4,4}$ (not planar) and any bipartite graph with two degree-2-vertices, four degree-three-vertices, and the remaining vertices degree 4, such that the degree-2-vertices are opposite in a $C_4$. If you want it connected, reroute a couple edges between the two parts, keeping all degrees the same, and keeping $K_{3,3}$ as a subgraph.

share|cite|improve this answer
Is this construction possible if the number of vertices is a multiple of 4? – Antony Della Vecchia Mar 22 '13 at 18:28
certainly. just start with a 4-regular bipartite graph with $2n$ vertices on each side, which contains a pair of vertices whose neighborhoods exact in exactly $2$ vertices. Delete $4$ edges (the edges incident to the symmetric difference of the two neighborhoods), and you are done. – Flo Pfender Mar 27 '13 at 2:27

Your Answer


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.