Components of bipartite graphs that are trees - MathOverflow 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 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>