retagged by
1,110 views
4 votes
4 votes

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 $\text{u,v,w }$ be three distinct vertices in $G.$ How many simple paths are there from $\text{u to v}$ going through $\text{w?}$

retagged by

1 Answer

Best answer
9 votes
9 votes
It is fixed that w has to be in path and path can include other vertices also, it can include 1,2,3,4 and even path can contain all vertices.

So total paths=

7C0× 1!+7C1×2! +7C2×3! + 7C3×4! + 7C4×5! +7C5×6! + 7C6×7!+ 7C7× 8!=95901
selected by

Related questions

2 votes
2 votes
1 answer
2