How can I show that every bipartite graph of maximum degree d is a subgraph of some d-regular bipartite graph.
If something I'm saying could be better mathematically phrased, please let me know. Let's call H our original bipartite graph. Suppose X and Y are the disjoint sets in H. If X has less vertices than Y, we add until equal. Same thing vice versa. Let's say this brings us to a total of d+x vertices on each side. My thought process is, if we can prove that we can create a d regular bipartite graph using the 2(d+x) vertices, H is a subgraph of this new graph. Is this a reasonable approach, if so, how can I go about completing it?