most recent 30 from http://mathoverflow.net 2013-05-22T19:21:26Z http://mathoverflow.net/feeds/question/70270 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/70270/components-of-bipartite-graphs-that-are-trees hungrygrad 2011-07-13T22:04:11Z 2011-07-13T22:04:11Z

<p>Hi, I apologize if this question is poorly formed as I'm not a graph theorist. I've figured out how to encode some information about a problem in surface topology in the language of graph theory. I just can't figure out how to prove it in graph theory or where to look for more information.</p> <p>Given some $n$, suppose I have two sets of vertices $V={v_1,...,v_k}$ and $W={w_1,...,w_l}$ with $k,l$ strictly less than $n$ where each vertex is assigned a degree $d_{v_i}$ or $d_{w_j}$, respectively. Suppose I know there exists a bipartite graph with $n$ edges from $V$ to $W$ respecting the given degrees of each vertex that is a forest. I would like to be able to say that this implies every bipartite graph with $n$ edges from $V$ to $W$ that respects the given degrees contains a component that is a tree. Is there any chance this is true or any references that could help me figure it out? I do also have the additional information that the only cycles I can allow are 2-cycles. Does this help anything?</p>