combinatoricsgraph theory
Draw a planar graph with two vertices of degree 3 and four vertices of degree 5, if possible.
Attempt:
With handshaking lemma, I get this:
$2e = 26 \implies e=13$
Then with Euler's formula, I get:
$6-13+f=2 \implies f = 9$
However, since $e \leq 3v – 6$ for a simple, connected, planar graph I would get:
$13 \leq 3(6)-6$
$13 \leq 12$
I can't figure out how I could get 9 faces for my graph. I can only get 8 faces as shown here:
This is the best attempt I had on this problem with no success.
Yes your ideas are correct. For the sake of not leaving this question unanswered, I'll refine your proof a bit.
Proofs in graph theory have a tendency to naturally be broken into cases like your proof above. A lot of the time though, this isn't necessary, and you can make a proof more concise by trying to combine cases.
For example, in your proof, separating out the case where $n=2$ is not necessary. The inequalities in your $n > 2$ case covers it. In fact explicitly stating a base case is often only necessary when you are arguing by induction. Also separating the cases where there is one vertex of degree at most five and no vertices of degree at most five is not necessary. Since $6n \geq 6(n-1) + \operatorname{deg}(v_k)$, your work for the first cases actually covers both cases.
Theorem: For $n \geq 2$, a planar graph with $n$ vertices must have at least two vertices with degree at most five.
Proof $\;$ First note that if this theorem holds for connected graphs, then it must hold for non-connected graphs as well because we can consider a single component and find the required two vertices with degree at most five.
Let $G$ be a connected planar graph with $n \geq 2$ vertices and $e$ edges. Suppose for the sake of contradiction that $G$ has at most one vertex, call it $v_k$, of degree less than or equal to five. Then by the handshaking lemma we have $$ 2e = \!\!\!\sum_{v_i \in \operatorname{V}(G)}\!\!\!\operatorname{deg}(v_i) \geq 6(n-1) + \operatorname{deg}(v_k) \geq 6n-1\;. $$ But since $G$ is planar and connected we know that $e \leq 3n-6$, getting us the contradiction $$ 6n-1 \;\leq\; 2e \;\leq\; 2(3n-6) = 6n-12\;. $$ Therefore there must be at least two vertices of degree at most five.
Let $G$ be a cubic planar graph with one hexagonal face and four square faces. By Euler's formula $$V-E+F=2,$$ where $F=7$ and $E=\tfrac32V$, and hence $V=10$. Let $G_1$ and $G_2$ be the induced subgraphs on the vertices of the hexagonal face, and on the remaining $4$ vertices respectively. Without loss of generality $G_2$ lies inside the hexagon $G_1$. Because $G$ is cubic there are precisely $6$ edges going out from $G_1$, hence going into $G_2$. It follows that there are precisely $3$ edges in $G_2$. As $G$ does not contain triangular faces $G_2$ is either a claw or a path.
If $G_2$ is a claw then each of the three leaves is adjacent to two vertices in $G_1$. Then removing the root of the claw from $G$ we can smooth out the remaining three leaves of $G_2$ to get a new planar graph on the vertices of $G_1$. Because $G$ is triangle-free this smoothing out produces three distinct edges that are not edges of $G_1$. But there is no such planar graph, a contradiction.
If $G_2$ is a path then contracting the edges adjacent to the terminal vertices yields two vertices that are each adjacent to three distinct vertices of $G_1$. As this graph is planar, it is the following graph:
Because $G$ is triangle-free the two terminal vertices of $G_2$ are adjacent to non-adjacent vertices in $G_1$, i.e. to the vertices on the left and right in the picture. Then the two middle vertices of $G_2$ are adjacent to the top and bottom vertices of $G_1$ in the picture. This is impossible as $G$ is planar.
Ths shows that there is no cubic planar graph with one hexagonal face and four square faces.
Best Answer
Here is a planar example. The vertices A and B are linked by two simple edges. The vertices A, B, E and F have degree 5. The vertices C and D have degree 3.