The constraint is not on the number of neighbors directly. If there is just one node (say, A) with 4 neighbors (say B1, B2, B3, B4), we can color A red and B1,

The constraint is not on the number of neighbors directly. If there is just one node (say, A) with 4 neighbors (say B1, B2, B3, B4), we can color A red and B1, B2, B3, B4 blue. It only becomes a problem when all nodes are interconnected (i.e. the graph is complete). So, the result does imply that graphs which are not colorable with 4 colors are not planar. In particular, the complete graph (where all nodes of the graph are connected) with 4 nodes is not planar.