Consider a graph $G$ whose edges are labelled $\{1, 2, ..., k\}$. Then the set of spanning trees is a collection of subsets of $[k]$.

a) Let $T$ = $\{\{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}\}$. Can $T$ be the collection of spanning trees of a simple connected graph?

b) Let $2\leq{n}$. Consider the collection $U_{2,n}$ of subsets of $[n]$ of size $2$. For what values of $n$ is $U_{2,n}$ the collection of spanning trees of a a connected graph?

To be honest I'm confused as to what these questions are asking in the first place. The numbers in $T$ refer to actual edges (so edges are labelled $1, 2, ...$ , not the edge between vertices $1$ and $2$, etc.)

If a graph has 4 edges and is simple and connected, then it can either have 4 or 5 vertices, right? Then does that mean $T$ does contain all the spanning trees of a specific graph since every edge is covered in there? For instance say I have a graph $G=(V,E)$ where I have $V$={a, b, c, d, e} and edge 1 = (a,b), edge 2= (a, c), edge 3 = (a, d), and edge 4 = (d, e). Technically the only spanning tree would be itself, right?

*I could even have the graph have edges 1=(a,b), 2=(b, c), 3=(c,d), 4=(d, e) and the only spanning tree would be one containing all edges.

Am I completely missing the point of this question? I'm so confused.


As I've used it, the definition of a spanning tree is a tree that contains all the vertices in some graph, not the edges. In this case, for a), $T$ cannot be the collection of spanning trees because not every member of $T$ can be a spanning tree. We can assume that our graph $G$ has four nodes (no simple graph of three nodes can have four edges and it's not possible to span five nodes with two edges). For example, if $(1,2)$ is a spanning tree, then $(1,3)$ cannot be one because given that $G$ is simple, $2 \ne 3$.

Regarding b), $U_{2,n}$ may contain all spanning trees for higher values of $n$, but for $U_{2,n}$ to strictly equal the set of spanning trees of a connected graph, $n \le 3$.

| cite | improve this answer | |
  • $\begingroup$ I see, I guess I wasn't looking at the set as each {1, 2} etc. being its own spanning tree. I thought maybe you could just take all the elements of $T$ but thinking about it now each element {i,j} standing for a possible spanning tree makes more sense. Thanks! $\endgroup$ – Karen M. Mar 27 '15 at 3:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.