Counting spanning trees and hamiltonian paths

2k Views Asked by At

Assumption : For any connected graph, every hamiltonian path is a spanning tree but not the other way around.

If the assumption is wrong there is no need of reading any furhter. So is the assumption correct ?

We have numerous algorithms to find all spanning trees of a connected graph. So, according to the assumption, haven't we already found all hamiltonian paths and thus MAYBE all hamiltonian circuits ?

If the above statements are correct, are we verifying(NP) the solution or are we finding(P) it ?

Please correct me if I'm wrong.

1

There are 1 best solutions below

2
On BEST ANSWER

Yes what you said its true - given a graph $G$ its a hamiltonian path is a spanning tree of $G$ and not every spanning tree of $G$ is a hamiltonian path.

With respect to what you say later on, we do have efficient algorithms for counting the number of spanning trees not finding all of them. Indeed the number of spanning trees is in general an exponential quantity hence there is no chance of having a efficient (polynomial time) algorithm for this problem.