## 3 Answers

This is not a solution. I want to ask in these spanning trees of K4. Which two spanning trees does not have a common edge??

### 4 Comments

Wrong..

Because such spanning trees will be in a **pair. **If you include one set then you cannot include another tree because then it will have edge in common.

For example, if you choose any one tree from row 2 then you can only have one tree from row 4 that will not have common edge. Hence its a pair.

For unlabelled graph **only possibility is maximum 2 trees** that have complimentary edges and those trees will be the **lines**.

Number of such **pairable** trees will be equal to number of ways we can label the n vertices of a graph. For K4 it is equal to n!/2 that is 4!/2 = 12. You can pick any one tree from row 2 , 3 and 4 and you'll definitely get its complimentary edged tree.