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.

| cite | improve this answer | |
  • $\begingroup$ Sorry, it was supposed to be $n^2$ edges $\endgroup$ – Lstan14 Apr 14 '19 at 16:16
  • $\begingroup$ Nvm, that makes a lot of sense. Thank you! $\endgroup$ – Lstan14 Apr 14 '19 at 16:18
  • $\begingroup$ Yes I saw there were $n^2$ edges, which is why going from $n^2$ to $(n+1)^2$ you add $2n+1$ edges $\endgroup$ – Ross Millikan Apr 14 '19 at 16:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.