The Gateway to Computer Science Excellence
+37 votes
Let $G$ be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers $1, 2,\ldots, 100.$ There is an edge between vertices $u$ and $v$ if and only if the label of $u$ can be obtained by swapping two adjacent numbers in the label of $v$. Let $y$ denote the degree of a vertex in $G$, and $z$ denote the number of connected components in $G$. Then, $y+10z$ = ____
in Algorithms by Boss
edited by | 6.8k views
A simple way to solve this is to recognise that any sequence of elements can be sorted by just swapping adjacent elements - that's the whole premise of bubble sort.

So if we assume that vertex 1 was in sorted order, we can see that every vertex can be brought to the sorted order, and thus, all of them are in the same component.

4 Answers

+133 votes
Best answer

Answer: 109


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 $\left \{ 1,2,3,4 \right \}$. So, we have vertices like $\left \{ 1,2,3,4 \right \}$, $\left \{ 1,3,2,4 \right \}$, $\left \{ 4,1,3,2 \right \}$, ... etc.

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

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

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

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

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

The given $3$ are the only permutations we can get by swapping only $2$ adjacent numbers from $\left \{ 1,2,3,4 \right \}$. So, the degree of vertex $\left \{ 1,2,3,4 \right \}$ 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 $\left \{ 1,2,3,4 \right \}$ we can reach to other vertex, say $\left \{ 4,3,2,1 \right \}$ by the following path:

$\left \{ 1234 \right \}$ -> $\left \{ 1243 \right \}$ -> $\left \{ 1423 \right \}$ -> $\left \{ 4123 \right \}$ -> $\left \{ 4132 \right \}$ -> $\left \{ 4312 \right \}$ -> $\left \{ 4321 \right \}$

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*1 = 109

by Boss
edited by
thank you for such a good explanation
well explained
there is  100! vertices but not 100 so why you take number of vertices will be 100?
Can you explain with graphs?
He has not taken 100 or 4 vertices, he has taken 4! only. Go through that again.

@suneetha 100! vertices each having label of 100 distinct numbers.

That was really a simplified explanation.
I think if you take just $\mathbf{n=3}$, then it would be even more easier.
i think question  trying to relating the concept of complete graph

@Ram Swaroop

It won't be a complete graph, it will rather be a cycle graph.

any node can only connect to 99 other nodes because only 99 adjacents can be created from one node so the degree will be 99

but for a complete graph every node will have degree = 100! - 1

+3 votes
$\mathbf{\underline{\color{blue}{An\;Easier \;approach:\Rightarrow}}}$



Take $\mathbf{n=3}$, then the number of vetices $=\mathbf{3!}$

Now, possible numberings for $\mathbf{"123"}$ are:

$\mathbf{213,132}\Rightarrow$ Number of degrees.

$\therefore$ For $\mathbf{n=3}$.

Degree $=2 = \mathbf{n-1}$

$\therefore$ For $\mathbf{100!}\;\;\;$ Degree $=\color{blue}{\underline{99}}$

For $\mathbf{n=3}$, Number of connected components $=\color{blue} 1\;\;\text{[$\;\because$ Only 1 triangle is possible.]}$

$\therefore$ For $\mathbf{n=100!}$, Number of connected components possible $=1$

$\therefore \;\mathbf{y = 99, z = 1}\\ \therefore 99 + 10\times 1 = 109.$

Hence, $\mathbf{109}$ is the correct answer.
by Boss
edited by

Only 1 triangle is possible.

for n=3 we will get a hexagon, not a triangle since we have 3! vertices.

No, I am talking about the connected components.
+2 votes

Please refer the page that i post below:



reshown by
0 votes
G is a graph with 100! vertices. Label of each vertex obtains from distinct permutation of numbers “1, 2, … 100”.
There exists edge between two vertices iff label of ‘u’ is obtained by swapping two adjacent numbers in label of ‘v’.
12 & 21, 23 & 34
The sets of the swapping numbers be (1, 2) (2, 3) (3, 4) … (99,100).
The no. of such sets are 99 i.e., no. of edges = 99.
As this is regular, each vertex has ‘99’ edges correspond to it.
So degree of each vertex = 99 = y.
As the vertices are connected together, the number of components formed = 1 = z
y + 102 = 99 + 10(1) = 109
by Active

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,218 questions
59,890 answers
118,128 users