Proof that it exists at least one graph G planar, bipartite and with $\delta$(G) $\ge$ 4

Question

I know this is possible, but how can I rationally get to an answer rather than just trying to draw several graphs until I find one?

Answer 1

Let $v$ denote the number of vertices, let $e$ deont the number of edges and $f$ denote the number of faces.

The graph is planar so $v-e+f=2$ (Euler).

The graph is bipartite so only contains even faces $f=f_4+f_6+\cdots$ (where $f_4$ is the number of quadrilateral faces, $f_6$ denotes the number of hexagonal faces, etc...) The edges can be double counted to give $2e=4f_4+6f_6+\cdots$.

Now suppose each vertex has valency exactly $4$ so $e=2v$. (A higher valency will make things worse.)

Multiply the equation $v-e+f=2$ by $4$ and one will rapidly derive a contradiction. So no such graph can exist.

Answer 2

Additionally to the other answer, you can have such a graph, if it doesn't need to be finite.

Given $\mathbb R^2$ to draw on'*, take $(0,0)$ as a vertex, let this be $G_0$. For $G_1$ add $(-1,-1)$, $(-1,1)$, $(1,-1)$ and $(1,1)$ as vertices and connect each of it to $(0,0)$, so $G_1$ is the star graph with 5 vertices. To get from $G_n$ to $G_{n+1}$, for each vertex $v$ of $G_n$ that has not yet degree $4$ (i.e. all leaves of $G_n$) do the following. If $v=(v_x,v_y)$ is connected to another vertex below, add the vertices $(v_x+(\frac{1}{2})^{n},v_y)$, $(v_x-(\frac{1}{2})^{n},v_y)$ and $(v_x,v_y+(\frac{1}{2})^{n})$ to the intermediate graph and connect them to $v$. The other directions (above/left/right) are to be done likewise. After this is done for all endvertices of $G_n$, we have $G_{n+1}$.

Now we have a series of graphs $G_0,G_1,G_2,\ldots$ and we can take their union $G=\bigcup_{n=0}^{\infty}G_n$, this is the graph with vertex set $\bigcup_{n=0}^\infty V(G_n)$ and edge set $\bigcup_{n=1}^\infty E(G_n)$. Since all $G_n$ are trees and we have $V(G_0)\subset V(G_1)\subset V(G_2)\subset\ldots$ as well as $E(G_0)\subset E(G_1)\subset E(G_2)\subset\ldots$, $G$ is also a tree (i.e. a connected acyclic graph). Such trees are bipartite and also more or less planar. It depends a bit on your definition on planarity, really, but if we take $\frac{1}{2+\varepsilon}$ instead of $\frac{1}{2}$, it should be planar in every sense you can extend planarity to infinite graphs (with factor $\frac{1}{2}$ the tree ends will touch, with factor $\frac{1}{2-\varepsilon}$ the edges and depending on $\varepsilon$ also the vertices will intersect).

Oh, and by construction, of course we have $\delta(G)=4$. In fact, this can be done for any $k\in\mathbb{N}$, you just have to adjust your scaling factor and the angles (we had right angles, so we could easily give coordinates for the vertices resulting from $v=(v_x,v_y)$. If $k=2m$, we get a representation of the Caley graph on $m$ free generators. The wikipedia page features the image where my construction is inspired from.

'* note that I write "draw on", but I use this figuratively, so you can image the resulting graph easier. We are actually constructing $G_n$ and $G$ completely by definition as a pair $(V,E)$ of vertices and edges, so this is as "rational" as you can get.