1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\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.
    Commented Mar 27, 2015 at 3:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .