1

Find the number of spanning trees contained in $G$.

The graph $G$ has vertex set $V = \{v_1,\ldots,v_8\}$ and edge set $E = \{e_1,\ldots,e_{10}\}$, where $e_1 = \{v_1, v_2\}$, $e_2 = \{v_2, v_3\}$, $e_3 = \{v_2, v_4\}$, $e_4 = \{v_3, v_4\}$, $e_5 = \{v_3, v_5\}$, $e_6 = \{v_5, v_6\}$, $e_7 = \{v_5, v_7\}$, $e_8 = \{v_6, v_7\}$, $e_9 = \{v_6, v_8\}$, $e_{10} = \{v_7, v_8\}$.

I'm thinking that I need to draw some kind of graph first in order to determine the number of spanning trees.

Carlos Eugenio Thompson Pinzón
  • 2,780
user3003255
  • 107
  • 1
  • 1
  • 4
  • 2
    I would certainly begin by drawing $G$. When you do, you should find two edges that must be present in every spanning tree. You’ll also find two separate parts of the graph where you have some choice in the edges that you keep; you should deal with each of them separately. – Brian M. Scott Dec 01 '13 at 02:49

1 Answers1

4

Here’s a rough sketch of $G$:

              1---2---3   6---8  
                  |  /|  /|  /  
                  | / | / | /  
                  |/  |/  |/  
                  4   5---7

Every spanning tree must include the edges $\{1,2\}$ and $\{3,5\}$. A spanning tree must include exactly two of the edges in the triangle $\{2,3,4\}$; they can be chosen in $3$ different ways. The trickiest bit is the subgraph with vertices $5,6,7,8$; see if you can count the spanning subtrees of that four-vertex subgraph. Each of them can be combined with any of the $3$ possibilities for the triangle $\{2,3,4\}$; use that to finish off the problem. I’ve left the rest of the solution spoiler-protected in case you get completely stuck.

Clearly any spanning tree must include at least one of $\{5,6\}$ and $\{5,7\}$, and it might include both. If it includes just one of them, it must include exactly two of the edges in the triangle $\{6,7,8\}$; that’s a total of $3$ possibilities for each each of the edges $\{5,6\}$ and $\{5,7\}$, for a total of $6$ possibilities. If it includes both, it must include exactly one of the edges $\{6,8\}$ and $\{7,8\}$; that’s another two possibilities for a total of $8$. Each of these $8$ can be combined with any of the $3$ ways to span the triangle $\{2,3,4\}$, so $G$ has altogether $3\cdot8=24$ spanning trees.

Brian M. Scott
  • 616,228