Graph theory - planar and hamiltonian graphs

Solution 1:

The graph is non-planar by Kuratowskis theorem: One of the three „needles“ together with a path from the tip to the bottom through the rest of the graph constitutes a $K_5$-minor.

The graph is not hamiltonian: Suppose there is a hamiltonian cycle and consider one of the needles. Pick a vertex inside the needle, which by definition has to lie on the cycle, and so do the tip and bottom of the needle. Now note that we can replace the corresponding tip-bottom part of the hamiltonian cycle with any tip-bottom-path inside the needle, which happens to meet every vertex of the needle (ie which is a hamiltonian path for the needle). Hence for the purpose of having a hamiltonian cycle it is equivalent to consider the same graph but with all inner vertices of the needle contracted to a single vertex. Because we may repeat the argument for every needle, we might as well consider the graph obtained from the original by replacing all three needles by new subgraphs of the form $\bullet - \bullet - \bullet$ drawn vertically). But this new graph doesn’t admit an hamiltonian cycle (concluded by inspection), which gives a contradiction.

Solution 2:

It contains a subgraph homeomorphic to $K_5$. So it is not planar.

It is not Hamiltonian. Contract each $K_4$ in the middle to a single vertex, because if there were any Hamiltonian path, once it touches 1 vertex of such a $K_4$ it must immediately pass through the other 3. Color the vertices on the top red, the ones in the middle green and the ones on the bottom blue. Then a Hamiltonian path would have to follow the pattern rgbbgrrgb and then it is stuck or else rgbbbgrrg and then it is stuck. Once you traverse a rgb vertical path the only way to come back to the top r is through another r and the only way to come back to the bottom b is through another b. So you cannot go from b to r in the first case. And you cannot go from g to r in the second case.