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?}$ Graph Theory discrete-mathematics graph-theory complete-graph virtual-gate-test-series + – Samujjal Das asked Jan 24, 2017 retagged Apr 14, 2019 by Lakshman Bhaiya Samujjal Das 1.1k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Rahul Jain25 commented Jan 24, 2017 reply Follow Share 60,621??? 0 votes 0 votes Samujjal Das commented Jan 24, 2017 reply Follow Share 95901 is given as answer 0 votes 0 votes dd commented Jan 24, 2017 reply Follow Share $n$ vertices complete graph $u,v,w$ are three distinct vertices. We need to finds simple paths from $u$ to $v$ via $w$. A simple path does not have repeated vertices and loops. Minimum path length from $u$ to $v$ via $w$ = $2$ Maximum path length from $u$ to $v$ via $w$ = $(n-1)$ For additional paths of length $(k+2)$ where $(k+2)$ $\leq$ $(n-1)$ $\rightarrow$ Select $k$ more vertices from { $\color{red}{\bf V}$ - {$\color{red}{\bf u,v,w}$} } in $\binom{n-3}{k}$ ways Permute those $k$ vertices along with $w$ in $(k+1)!$ ways. Total paths $\rightarrow$ = $\begin{align*} \sum_{\bf k=0}^{\bf n-3}\binom{\bf n-3}{\bf k}*\bf \left ( k+1 \right ) \bf ! \end{align*}$ = $95901$ as explained in the answer below. 4 votes 4 votes Please log in or register to add a comment.
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 Rahul Jain25 answered Jan 24, 2017 selected Jan 24, 2017 by Samujjal Das Rahul Jain25 comment Share Follow See all 3 Comments See all 3 3 Comments reply Samujjal Das commented Jan 24, 2017 reply Follow Share Elaborate a bit more please!! 1 votes 1 votes Rahul Jain25 commented Jan 24, 2017 reply Follow Share First vertex and last vertex are fixed. Also w is fixed but not its position. So out of remaining 7 vertices I can select no vertex or 1 vertex or 2 vertex ,3,4,5,6,7 after sleecting them, suppose 3 vertuces are selected from those 7 by using 7C3 then these 3 along with w can be arranged in 4! And same for all other paths. Remember this is complete graph edge is there berween every pair of vertices. 2 votes 2 votes Samujjal Das commented Jan 24, 2017 reply Follow Share Understood. Nice explanation!! 1 votes 1 votes Please log in or register to add a comment.