Finding number of vertices on a graph G

Question

The question given is from a workshop in preparation for my upcoming exam:

A simple graph is called regular if all vertices have the same degree. Let G be regular with $22$ edges, how many vertices can G have?

My first thought, and frankly only thought, is to use the handshaking lemma. Where the handshaking lemma states: 'A finite graph has an even number of vertices with odd degree'

This can easily be seen by simply taking a graph with $22$ vertices with degree $2$, From this lemma we have $\sum_{x\in V(G)} = 2|E(G)|$

However I'm unsure how i can use this to find the number of vertices in G.

Answer 1

Let $G$ have $n$ vertices each with degree $d$. Then the sum of all degrees is twice the number of edges, i.e.$$nd=44$$Now we are interested in natural number solutions for the above equation which may represent a simple graph, assuming you want simple $G$.

For example, $n=1,d=44$ is not a feasible solution since it represents a single vertex with $22$ self-loops. You may recall that in a simple regular graph of $n$ vertices, the maximum degree of the vertices can be $n-1$; i.e.$$d<n\implies nd=44<n^2\implies n\ge7$$This narrows-down the search. The solutions are $n=11,d=4$ and $n=22,d=2$ and $n=44,d=1$.

Answer 2

Suppose the graph has $n$ vertices, each of degree $d$.

Then, the total number of edges in the graph will be $\frac{nd}{2}=22.$ So, $nd=44 \Rightarrow (n,d) \in \{(1,44),(2,22),(4,11),(11,4),(22,2),(44,1)\}$.

Assuming multiple edges between vertices are not allowed, we must have $d\leq n-1$.

So, the possible solutions are $n=11, \ d=4$ or $n=22, \ d=2$ or $n=44, \ d=1$.

You then need to check that all of these possibilities give a feasible graph. For $d=1$ you get a bipartite graph, for $d=2$ you get a circular graph, and for $d=4$, you can also find an example.