Could there exist a planar graph with the following degrees of vertices: {5, 5, 4, 4, 4, 2}

Question

I was wondering if a graph existed because I used euler's inequality and it said that theres supposed to be a graph but im having a hard time figuring out what it is. Thank you!

Answer 1

Up to graph isomorphism, there exists only one graph with those vertex degrees. If we call the vertices $v_1,\dots, v_6$ where degree of $v_1$ and $v_2$ is $5$, and the degree of $v_6$ is $2$, then we know:

1. $v_1$ and $v_2$ must be connected to all other vertices.
2. $v_6$ is connected to $v_1$ and $v_2$ because of (1), and can have no other connections because it has degree $2$.
3. Vertices $v_3,v_4$ and $v_5$ cannot be connected to $v_6$ (because of (2)), therefore, they are all connected to all other vertices.
4. Therefore, $\{v_1,v_2,v_3,v_4,v_5\}$ is a fully connected subgraph of the original graph.

So, your graph is basically just $K_5$, with one more vertex connected to two of its nodes. And it's well known that $K_5$ is not planar.

Answer 2

Here is an example of the required planar graph.

Answer 3

Here’s a graph with the degrees you specified: