You need the graph to be embedded in the plane (that is, drawn with no edges crossing) to have faces defined. Also, I think your graph is not planar. The condition you are using works like this "If the graph is planar, then " but the latter doesn't prove the first, that is "If , then the graph is planar" is WRONG.