0
$\begingroup$

$K_n$, the complete graph on $n$ vertices, is the simple undirected graph in which every vertex shares an edge with every other vertex. Suppose that $j$ edges $(3 \leq j \leq n)$ of $K_n$ are chosen at random. What is the probability that these edges form a circuit?

My attempt at a solution was as follows:
Since the total number of edges of a complete graph on $n$ vertices is $C(n,2)$, the total sample space of ways to choose $j$ edges from $K_n$ would be $C(C(n,2),j)$. $$ \therefore \text{Sample space} = C(C(n,2),j).$$ Because $K_n$ is complete, any given subset of vertices is connected. Therefore, we can choose any $j$ vertices from $K_n$ and the resulting edges formed will always form a circuit. $$ \therefore \text{Event} = C(n,j), \text{ probability} = \frac{C(n,j)}{C(C(n,2),j)}.$$ However, the answer is given to be $$\frac{C(n,j)[\frac{1}{2}(j-1)!]}{C(C(n,2),j)}.$$ What accounts for $[\frac{1}{2}(j-1)!]$?

EDIT 1. Upon reexamination of the problem, I am guessing that $[\frac{1}{2}(j-1)!]$ accounts for multiple possible circuits from the edges formed from a given subset of $j$ vertices. However, I am still unsure of how the number of ways results in exactly $[\frac{1}{2}(j-1)!]$.

EDIT 2. To answer my own question:
A subset of $j$ vertices of $K_n$ forms its own complete graph $K_j$ on $j$ vertices. The number of circuits formed with $j$ vertices on $K_j$ is $[\frac{1}{2}(j-1)!]$.

$\endgroup$
0
$\begingroup$

A subset of $j$ vertices of $K_n$ forms its own complete graph $K_j$ on $j$ vertices. The number of circuits formed with $j$ vertices on $K_j$ is $[\frac{1}{2}(j-1)!]$, since it is equivalent to finding the number of free circular permutations in $j$ elements (consider each vertex to be a distinct element; any given circuit of length $j$ is equivalent to the elements arranged in a circular fashion).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy