0
$\begingroup$

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)

  • 0
    If we use contradiction means that not exists a k-regular bipartite graph . we can use vertices and edges H to get contradiction?2019-03-14

1 Answers 1

1

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$.

  • 0
    @World: While thinking about how to improve the explanation, I realized that there’s a hole in my proof. I think that I can patch it, but it may take a little while.2012-10-29