Given a relation count the vertices and edges of a 4-regular graph

Question

I'm trying to solve this problem.

$G$ is a 4-regular connected graph. It exists the following relation between the number of edges ($E$) and the number of vertices ($V$): $E=3V-6$. How many vertices and edges does G have?

My answer: Since the number of $E$ must be even I need to choose a certain value for $V$ such that $E$ is even but I can also draw a 4-regular connected graph. So I found $V=8$ such that I can draw a 4-regular connected graph. So $G$ has $8$ vertices and $18$ edges.

Are my result and reasoning correct? Although I only tried two values for $V$ before I got to this result, could it be solved more directly? Maybe without even trying to draw the graph to see if the chosen values were appropriate?

Answer 1

For any $r$-regular graph, on $n$ vertices and $m$ edges, there exist the following relation : $$ 2m = \sum_{i=1}^n d(i) = r\cdot n$$

Therefore in your case we have the relations : $$ \left\{ \begin{array}{l} m = 3n-6\\ 2m = 4n \end{array} \right.$$

Therefore $2n=3n-6$ and $n=6$ and $m=12$.

Note Since $m=3n-6$, then your graph is maximal planar, hence a triangulation, you can draw it as a rectangle, with diagonals (with the additional centre vertex), and an additional exterior vertice, connected to all four angles of your rectangle.

Answer 2

If a graph is $4$-regular then by the handshaking lemma $2E=4V$ and now you have two simultaneous equations.

If your graph for $8$ vertices is actually $4$-regular, it must have $16$ edges, not $18$.