I've encountered a question in my Graph Theory course that I don't quite understand. The instructor never went through what exactly the "function" used in this question is, so I'm looking for some clarification:
Show that if $e$ is an edge of $K_n$, then $\tau(K_n - e) = (n-2)n^{n-3}$.
He never discussed this $\tau(G)$ "function", so I looked it up in the textbook he references from time to time (Bondy and Murty's Graph Theory), which says
pg 504: $\tau(H)$ is the number of vertices in a minimum traversal of a hypergraph.
I am a bit confused as to what this question is asking; any clarification is deeply appreciated!
A spanning tree $T$ of an undirected graph $G$ is a subgraph that is a tree (= a connected undirected graph with no cycles) which includes all of the vertices of $G$, with minimum possible number of edges. For a connected graph with $n$ vertices, a spanning tree will have $n-1$ edges. For a complete graph $K_n$ with $n$ vertices, Cayley's formula gives the number of spanning trees as $n^{n − 2}$. From wikipedia we read a double counting proof for the Cayley's formula.
Following this answer we can count all the edges in all the possible spanning trees in two different ways:
According to the Cayley's formula there is a total number of $n^{n-2}$ spanning trees for the complete graph $K_n$. Each spanning tree has ${n-1}$ edges. The sum of all the edges in all spanning trees is therefore $(n-1)n^{n-2}$.
Another way of counting is: Assume that $k$ is the number of spanning trees, that contain an edge $e$. Note that an edge must not appear in every spanning tree of the graph, but it appears in $k$ spanning trees. Because $\binom{n}{2}=n(n-1)/2$ is the total number of edges in any complete graph $K_n$ with $n$ vertices, we calculate the sum of all the edges in all spanning trees as $k n(n-1)/2$.
$$(n-1)n^{n-2} = k n(n-1)/2 \Rightarrow k = 2n^{n-3}$$
So if we remove an edge $e$ we get the total number of spanning trees in a complete Graph $K_n$ as $$ n^{n-2}-k = (n-2)n^{n-3} $$