# Determining whether a certain graph is planar

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.

-

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