For a graph with $n$ vertices, what is the minimum number of edges such that each vertex is connected to atleast $3$ other vertices? How to find such a configuration?
I assume this to be a well known problem in graph theory, but since I'm not familiar with it I need some help figuring it out.
On
If $n$ is even, what you are looking for are cubic graphs, i.e. graphs, in which all of the vertices have the degree equal to $3$. Using the hand-shake lemma, we obtain that $$2|E| = n \cdot d \rightarrow |E| = \frac{3}{2}n$$
However, as you can see, the above only works for even $n$. For odd $n$, consider any cubic graph on $n$ vertices and add a vertex on any edge. This vertex already has degree equal to $2$, so you only need to add an edge to any other vertex to satisfy the $\delta$ requirement, so you have $$|E| = \frac{3}{2}(n-1)+2$$
Hint: if you sum the orders of each vertices (i.e. how many edges they are connected to), and each order is $\ge 3$, then your sum is $\ge 3n$. We have counted each edge twice, once for each vertex it is connected to, so that means we have at least $3n/2$ vertices (and for odd $n$, that means at least $(3n+1)/2$ as the number of vertices is an integer).
Now you know what bound you're looking for, have a go at finding a configuration. You might want to split your answer into cases, depending on the value of $n$ modulo particular integers.