Given an undirected graph $G=(V,E)$, use mathematical induction to show how to construct a graph with $2n$ nodes and $n^2$ edges such that the graph has exactly one, unique, complete pairing.
Note: A pairing is a set $P⊆E$ of edges such that for all $(u,v),(x,y)∈P$, the nodes $u, v, x, y$ are all different. In other words, no two edges in $P$ have a node in common. A complete pairing is a pairing P that uses all the graph’s nodes, that is, a pairing for which
$\bigcup_{(u,v)∈P}${$u,v$}$=V $.
I'm struggling a lot with how to approach this problem. I do understand what a pairing is and I can think of some example graphs with $2n$ nodes and $n^2$ edges s.t. there is a complete pairing (I've drawn a few) but I'm unsure how to approach it in terms of mathematical induction. I can't seem to figure out a base case without drawing a graph or how to approach it mathematically. Any ideas? I would really appreciate any help, hints or a start.
Look at your graphs for $n=1,n=2,n=3$. The fact that we are supposed to use induction suggests that the $n=1$ graph is a subgraph of the $n=2$ graph and the $n=2$ graph is a subgraph of the $n=3$ graph. Try to draw the graphs in a way that it is clear what is added as you go up in $n$.
When we go from $n$ to $n+1$ we have to add two vertices and $2n+1$ edges. I drew the vertices in two columns, with the top row being the $n=1$ vertices with an edge between them. Now put another pair below those and draw the $3$ edges you add to make the $n=2$ graph in another color. Put a third pair below those and draw the five edges you add to make the $n=3$ case in a third color.
You should be able to see a pattern in how you are adding edges. Your task in the induction is to describe that pattern and show that it can continue as long as you want.