Timeline for Components of bipartite graphs that are trees
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 25, 2018 at 19:03 | comment | added | D. Ror. | @hungrygrad If you are satisfied with the answers given, please accept the community wiki answer below so your question can be marked as answered. | |
| Mar 11, 2017 at 4:14 | answer | added | D. Ror. | timeline score: 2 | |
| Jul 14, 2011 at 13:09 | comment | added | hungrygrad | Oh, great, now it makes sense. Thanks so much! | |
| Jul 14, 2011 at 5:12 | comment | added | j.c. | @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. | |
| Jul 14, 2011 at 0:58 | comment | added | hungrygrad | 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. | |
| Jul 13, 2011 at 22:19 | comment | added | Clinton Conley | 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? | |
| Jul 13, 2011 at 22:04 | history | asked | hungrygrad | CC BY-SA 3.0 |