0
$\begingroup$

Question

Let $G$ be a Graph with $100!$ vertices,with each vertex labelled by a distinct permutation of the numbers $1,2,3,...100.$There is an edge between vertices $u$ and $v$ $\text{iff}$ the label of $u$ can be obtained by swapping two adjacent numbers in the label of $v$.Let $y$ denotes the degree of a vertex in $G$ ,and $z$ denotes the number of connected component in $G$.Then $y+10z=$___

My Approach

To find the number of edges,I will consider for vertex labelled $1$ to $100$. number of edges $=\frac{100}{2}=50$

and i got degree of every vertex i.e $y$= $1$ and number of connected components as $50$ i,e $50$ components with $1$ edges each.Hence i am getting answer as $1+50 \times 10=501$

Am i wrong? please help

$\endgroup$
1
$\begingroup$

Your approach is wrong. You misunderstood the question.
The vertices are labelled as a permutation of numbers from 1 to 100 as follows
for example one of the lable is :$ (1,2,3,4........100)$ This vertex can be connected to $(2,1,3.......100)$ ,$(1,3,2,....100)$ and so on to $99$ vertices. So each of the vertex has the same degree because there are 99 adjacent swaps possible in total in any permutation. So $y=99$ and we can reach to any permutation from a given permutation by a sequence of adjacent swap operations. So there is only a single component so $z=1$.

$\endgroup$
2
  • $\begingroup$ thanks Mayank , i got you .Can we say this graph is similar to line graph? $\endgroup$
    – laura
    Feb 14 '18 at 11:55
  • $\begingroup$ Not a line graph but a tree $\endgroup$ Feb 14 '18 at 12:14
1
$\begingroup$

Thought 1: You can get from any permutation to any other permutation via a sequence of swaps of adjacent values.

Thought 2: Among 100 slots there are 99 adjacent pairs of slots.

$\endgroup$
2
  • $\begingroup$ Thought1 : Isn't question saying $12 \rightarrow 21$ ? i mean $12$ is connected to $21$ $\endgroup$
    – laura
    Feb 14 '18 at 11:47
  • $\begingroup$ For example in the case of 4 vertices let's see that 1234 is (indirectly) connected to 2341. Here is a sequence of adjacencies: 1234, 2134, 2314, 2341. $\endgroup$
    – paw88789
    Feb 14 '18 at 11:48
0
$\begingroup$

Answer: 109

  • Explanation:

We have to find $2$ things here, the degree of every vertex(which will be same for all vertices) and number of connected components.

Instead of $100$, let's solve this by taking lesser value, say $4$.

With $4!$ vertices, each vertex is a permutation of $\{1,2,3,4\}$. So, we have vertices like $\{1,2,3,4\}, \{1,3,2,4\}, \{4,1,3,2\}, \ldots$ etc.

Here $\{1,2,3,4\}$ will be connected with

$$\{2,1,3,4\}$$ $$\{1,3,2,4\}$$ $$\{1,2,4,3\}$$

To get this list, just take $2$ adjacent numbers and swap them. eg. $\{1,2,3,4\}$ swap $1$ and $2$ to get $\{2,1,3,4\}$.

The given $3$ are the only permutations we can get by swapping only $2$ adjacent numbers from $\{1,2,3,4\}$. So, the degree of vertex $\{1,2,3,4\}$ will be $3$. Similarly for any vertex it's degree will be $3$.

Here we got $3$ because we can chose any $3$ pairs of adjacent numbers. So, with $n$, we have $n−1$ adjacent pairs to swap. So, degree will be $n-1$.

In our question, degree will be $100−1 = 99$

Now let's see how many connected components we have.

It will be $1$. Why?

If one can reach from one vertex to any other vertex, then that means that the graph is connected.

Now if we start with a vertex say $\{1,2,3,4\}$ we can reach to other vertex, say $\{4,3,2,1\}$ by the following path:

$$\{1234\} \to \{1243\} \to \{1423\} \to \{4123\} \to \{4132\} \to \{4312\} \to\{4321\}$$ Just take two adjacent numbers and swap them. With this operation you can create any permutation, from any given initial permutation.

This way you can show that from any given vertex we can reach any other vertex. This shows that the graph is connected and the number of connected components is $1$.

$y = 99$ and $z = 1$

$$y + 10z = 99 + 10\cdot 1 = 109$$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.