<p>Given a balanced bipartite graph G and a planar graph H. We do not know the number of perfect matchings in G and we do not know the number of spanning trees in H. But assume they are at least 3 both.</p>
<p>1.Can we construct in P, a balanced bipartite graph G', whose number of perfect matchings is one more than that for G?</p>
<p>We can ask same question as above with any <span class="math-container">$\#PE$</span> problem (<span class="math-container">$\#P$</span> problems with decision version in <span class="math-container">$P$</span>)</p>
<p>2.Can we construct in L, a planar graph H', whose number of spanning trees is one more than that for H?</p>

CC BY-SA 4.0
2023-08-18T00:50:44.623Z
If G itself is a perfect matching, then it only has 1 perfect matching. If H is a tree, it's planar but has only one spanning tree. Also, if a planar graph is disconnected it might have 0 spanning trees. Not crucial to the question itself, but did you mean to have some other assumptions or other conclusion in your first paragraph?
Joshua Grochow
CC BY-SA 4.0
2023-08-18T06:16:10.693Z
I am assuming the count is at least 2.
Turbo
CC BY-SA 4.0
2023-08-18T21:11:35.447Z
Okay, I guess that's a fine assumption. But now I'm curious: why do you want to assume they are at least 2?
Joshua Grochow
CC BY-SA 4.0
2023-08-18T21:14:56.900Z
Related: https://cstheory.stackexchange.com/a/51348/129. (But that explicitly doesn't answer this question, as the construction there will produce a graph whose *weighted* perfect matchings add up to perm+1, rather than unweighted.)
Joshua Grochow
CC BY-SA 4.0
2023-08-18T23:59:32.720Z
Just for genericity.. there are no graphs with #spanning trees =2
Turbo
<planar-graphs><permanent><bipartite-graphs><determinant><spanning-tree>
On perm+1 and det+1
Turbo
# On perm+1 and det+1

(Asked by: username_0 on 2023-08-15)

Given a balanced bipartite graph G and a planar graph H. We do not know the number of perfect matchings in G and we do not know the number of spanning trees in H. But assume they are at least 3 both.

1.Can we construct in P, a balanced bipartite graph G', whose number of perfect matchings is one more than that for G?

We can ask same question as above with any $\#PE$ problem ($\#P$ problems with decision version in $P$)

2.Can we construct in L, a planar graph H', whose number of spanning trees is one more than that for H?

**Tags:** planar-graphs, permanent, bipartite-graphs, determinant, spanning-tree

> **Comments:**
> **username_1**: If G itself is a perfect matching, then it only has 1 perfect matching. If H is a tree, it's planar but has only one spanning tree. Also, if a planar graph is disconnected it might have 0 spanning trees. Not crucial to the question itself, but did you mean to have some other assumptions or other conclusion in your first paragraph?  
> **username_0**: I am assuming the count is at least 2.  
> **username_1**: Okay, I guess that's a fine assumption. But now I'm curious: why do you want to assume they are at least 2?  
> **username_1**: Related: https://cstheory.stackexchange.com/a/51348/129. (But that explicitly doesn't answer this question, as the construction there will produce a graph whose *weighted* perfect matchings add up to perm+1, rather than unweighted.)  
> **username_0**: Just for genericity.. there are no graphs with #spanning trees =2  

---

## 0 answers

