Question

Let G be a bipartite graph of maximum degree k. Show that there exists a k – regular bipartite graph, H, that contains G as an induced subgraph.

Answer 1

Answer:

Suppose we have G is bipartite,

let the partitions of the vertices be X and Y .

Then let

X'= X ∩ H and Y' = Y ∩ H.

Suppose that this was not a valid bipartition of H – then we have that there exists v and u in X' (without loss of generality) such that v and u are adjacent.

But then by the definition of a subgraph, they are also adjacent in G.

But then X and Y is not a valid bipartition of G.

Therefore, H is a bipartite graph