# How to use induction to show how to construct a graph with $2n$ nodes and $n^2$ edges such that the graph as exactly one, unique, complete pairing?

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.
• Sorry, it was supposed to be $n^2$ edges – Lstan14 Apr 14 '19 at 16:16
• Yes I saw there were $n^2$ edges, which is why going from $n^2$ to $(n+1)^2$ you add $2n+1$ edges – Ross Millikan Apr 14 '19 at 16:53