Suppose that G be a bipartite graph with maximum degree of k.
Prove that:
1)Exists a K-regular bipartite graph that G be subgraph it(H)
Suppose that G be a bipartite graph with maximum degree of k.
Prove that:
1)Exists a K-regular bipartite graph that G be subgraph it(H)
First note that if $G=\langle U,V,E\rangle$ is a $k$-regular bipartite graph, then $k|U|=|E|=k|V|$, so $|U|=|V|$.
Now let $G=\langle U,V,E\rangle$ be a bipartite graph in which the maximum degree of any vertex is $k$. By adding isolated vertices if necessary we may assume that $|U|=|V|=n$, say. For each $w\in U\cup V$ let $f(w)=k-\deg(w)$; this is the number of edges that we need to attach to $w$ to raise its degree to $k$. Note that $\sum_{u\in U}f(u)=n^2-|E|=\sum_{v\in V}f(v)$.
Next, construct an auxiliary graph $G'$. For each $w\in U\cup V$ let $F_w$ be a new set of $f(w)$ vertices. Let $U'=\bigcup_{u\in U}F_u$ and $V'=\bigcup_{v\in V}F_v$. Then $|U'|=|V'|=n^2-|E|$, so we can choose a set $E'$ of $n^2-|E|$ edges in such a way that $G'=\langle U',V',E'\rangle$ is a $1$-regular bipartite graph, a perfect matching of $U'$ and $V'$.
Finally, let $E''=E\cup\Big\{\{u,v\}:u\in U,v\in V,\text{ and }E'\text{ contains an edge between }F_u\text{ and }F_v\Big\}\;,$
and let $H=\langle U,V,E''\rangle$; I leave it to you to check that $H$ is a $k$-regular extension of $G$.