MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

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?

share|cite|improve this question
I'm not sure I understand the problem, but a finite forest has strictly fewer edges than vertices. And a finite graph with no acyclic connected component has at least as many edges as vertices. Does this give you what you want? – Clinton Conley Jul 13 '11 at 22:19
Not quite. Both $k$ and $l$ are less than $n$, but their sum should be, so the total number of vertices is more than $n$, however the number on each side is less. – hungrygrad Jul 14 '11 at 0:58
@hungrygrad, let me rephrase Clinton Conley's argument in your notation. The existence of a forest on your sets of vertices with n edges implies that k+l>n. But there exist no graphs with k+l vertices all of whose connected components contain cycles (i.e. have no components that are trees), as all such graphs must have at least k+l edges, which was strictly greater than n. – j.c. Jul 14 '11 at 5:12
Oh, great, now it makes sense. Thanks so much! – hungrygrad Jul 14 '11 at 13:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.