0
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 5
    $\begingroup$ 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? $\endgroup$
    – Clinton Conley
    Commented Jul 13, 2011 at 22:19
  • $\begingroup$ 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. $\endgroup$
    – hungrygrad
    Commented Jul 14, 2011 at 0:58
  • 2
    $\begingroup$ @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. $\endgroup$
    – j.c.
    Commented Jul 14, 2011 at 5:12
  • $\begingroup$ Oh, great, now it makes sense. Thanks so much! $\endgroup$
    – hungrygrad
    Commented Jul 14, 2011 at 13:09
  • $\begingroup$ @hungrygrad If you are satisfied with the answers given, please accept the community wiki answer below so your question can be marked as answered. $\endgroup$
    – D. Ror.
    Commented Jun 25, 2018 at 19:03

1 Answer 1

Reset to default
2
$\begingroup$

Clinton Conley, Jul 13 '11 at 22:19 answered:

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.

j.c., Jul 14 '11 at 5:12 clarified:

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .