# Tag Info

3

The tree is correct and unique. The descendants of node $k$ are precisely the nodes $j\gt k$ for which $j$ appears before $k$ in post-order; that uniquely determines the tree you've drawn.

2

Your understanding is correct, but the reasoning could be explained more clearly: Clearly $\xi(G)$ is the sum of the degrees of the vertices of $G$, which is twice the number of edges. Thus, if $\xi(S)=\xi(T)$, then $S$ and $T$ have the same number of edges, $\frac{\xi(S)}2$. The number of vertices of a tree is one more than the number of edges, so ...

2

No. Take any connected graph with a vertex of degree one. All possible spanning trees must contain the edge containing that vertex.

1

Hint Let $x$ be the number of leaves and $y$ the number of internal vertices. Then the total degree is at least $$x+3y$$ By Handshaking Lemma (and tree formula), the total degree is exactly $$2(x+y-1)$$ Combine them.

1

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

1

Ans 1: For $n=1$, we have $0$ internal nodes and $1$ external node. Induction Hypothesis: The 2-tree with $n-1$ internal nodes has $n$ external nodes. Now, if you add $2$ nodes to one of the external node of a 2-tree with $n-1$ internal nodes, we get a 2-tree with $n$ internal nodes and the number of external nodes decreases by $1$ (since by adding $2$ ...

Only top voted, non community-wiki answers of a minimum length are eligible