Determine the number of vertices for the following graphs or multigraphs:
a) $G$ is a 3-regular graph and it has 9 edges?
b) Let $G$ be a regular graph with $|E| = 15$ and with at least $10$ vertices. Give all possible numbers of vertices that $G$ has?
c) $G$ has two vertices if degree $4$ and all others of degree $3$?
Ans: I tried to solve above problem using formula $V-E+F =2$ and $E \leq 3V-6$ but couldn't solve it completely. Let me know if anyone knows answer for this?
For (a), it's a handshaking question. So $\sum_{i=1}^{n} 3 = 2 * 9$. So $3n = 18$, which gives us six vertices.
(b) So $G$ is regular, which gives us $(10 + k)n = 30$, for $k \geq 0$. If $k = 0$, then $n = 3$. If we have $k = 5$, there are $15$ vertices each of degree two. We could also have $30$ vertices of degree $1$.
For (c), we again use the Handshake Lemma. So $4 * 2 + 3(n-2) = 2E$. So $2 + 3n = 2E$, which gives us $n = \dfrac{2(E - 1)}{3}$. Note that $n$ must be an integer, so $3$ divides $2(E - 1)$, which gives us $2E - 2 \equiv 0 \pmod{3}$, or $E \equiv 1 \pmod{3}$.
The formula you are using is Euler's formula, which you can use to test if the (connected) graph is planar. You aren't dealing with issues of planarity, so it's not relevant.