How many spanning trees are contained in $G$? 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.
 A: 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.

