829 views
0 votes
0 votes
Suppose a single tennis tournament is arranged among n players and the number of matches planned is a fixed number e (where n-1 < e < n(n-1)/2 ).For sake of fairness,how will you make sure that some players do not group together and isolate an individual (or a group of players).

1 Answer

1 votes
1 votes

Let us consider a graph G(n,e)  where each player represents a vertex (n) and each match represent an edge (e).

There exists an edge between 2 vertices if there is a match scheduled between the 2 players.

The problem is to make sure that the graph G is connected. We need to determine minimum number of edges needed so that the graph G is connected.

Solution:

Worst case: 1 vertex is not connected.

Maximum number of edges possible in such case is when the rest of the vertices (n-1) form a complete graph.

Here, edges possible =  (n-1)C2 = ((n-1)*(n-2))/2

Now, if we add just 1 more edge to this number, the vertex which was isolated will get connected.

Hence, e > ((n-1)*(n-2)) / 2  to make sure no player is left isolated.

Hope this helps!

Related questions

0 votes
0 votes
0 answers
1
Ayush Upadhyaya asked Jun 8, 2018
478 views
Show that a simple graph is nonseparable iff for any two given arbitrary edges a circuit can always be found that will include these two edges.
0 votes
0 votes
0 answers
2
Ayush Upadhyaya asked Jun 8, 2018
449 views
Show that a graph G is non-separable iff every vertex pair can be placed in some circuit in G.
1 votes
1 votes
2 answers
3
Ayush Upadhyaya asked Jun 2, 2018
1,597 views
Is every regular graph of degree d(d$\geq$3) non-separable?If not, give a simple regular graph of degree 3 that is separable.
0 votes
0 votes
0 answers
4
Ayush Upadhyaya asked Jun 2, 2018
654 views
Prove that in a connected graph G a vertex v is a cut-vertex if and only if there exist two(or more) edges x and y incident on v such that no circuit in G includes both x...