Question 6083 – Graph-Theory

A complete graph on n vertices is an undirected graph in which every pair of distinct vertices is connected by an edge. A simple path in a graph is one in which no vertex is repeated. Let G be a complete graph on 10 vertices. Let u, v, w be three distinct
vertices in G. How many simple paths are there from u to v going through w?

Correct Answer: A

Let V be the set of all vertices. A path between u to v through w is formed by a subset V ‘ of V \ {u, v, w} and forming a permutation of V’ ∪ {w}. Now for each i ≤ 7, there (7 i) are subsets V’ of size i, and (i + 1)! permutations of V’ ∪ {w}.
Thus the number of required paths is

This expands to
40320 · 1 + 5040 · 7 + 720 · 21 + 120 · 35 + 24 · 35 + 6 · 21 + 2 · 7 + 1 · 1 = 95901.