Graph Theory : Will it stop or not?

Question

I cannot find out how to start with this question:

A graph has n vertices and m edges.No two pairs of vertices can be connected by more than one edge.Rahul starts to play a game: He changes the edges in following manner -

• He selects one vertex, and adds an edge from that vertex towards all other vertex where the edges do not exist.
• and at the same time, deletes all pre-existing edges from that vertex.

This game will stop only when their exist a direct edge between every two Vertices. You need to determine whether it is possible to finish this game, or whether this will never happen, no matter what moves he make.

Input : Initial state of graph will be given. Output :"yes" or "no"

Can someone give a hint on how to start??

Answer 1

1) Order of moves doesn't matter (since you can exchange any two subsequent moves to the same result);
2) Two subsequent changes with the same vertex have zero effect;
3) You can get to final state iff. you can get there changing any vertex no more than once;
4) Any two connected vertices must be both changed or both unchanged, of any two vertices not connected exactly one should be changed.

Take a connected component in the graph. Vertices there should all change or all remain unchanged. If the component isn't fully connected, finishing the game is impossible. If there are at least three connected components, finishing the game is impossible. If there are exactly two fully connected components, all vertices in exactly one of them should be changed.

Answer: the game can be finished if and only if the graph either is already fully connected or consists of two fully connected components. (It's easy to see that when the graph consists of two fully connected components, changing a vertex effectively moves it from one component to another.)

Algorithm to check for the answer: suppose we are given a number of vertices n and then a list of edges in form (a,b) where a and b are vertex numbers from [1,n]. Let vertices be an array of records (num_edges, connected, sample), initialized with (0,k,k) (k is vertex number). Then for each edge (A,B):

1. increase num_edges for A and B by 1;
2. if A.sample equals B.sample, go to next edge;
3. exchange A.connected and B.connected, starting from A.connected vertex set sample to A.sample and follow connected until reaching B; got to next edge.

Finally check that all vertices starting from 1 and following connected have the same num_edges equal to (their number - 1) and all remaining vertices for similar loop. Time should be O(max(n log(n), m)), memory O(n).

Answer 2

A solved graph with n vertices will be a complete graph k_n with ½n(n-1) edges.

Flipping the state of a vertex will mean that the vertex becomes disconnected from the graph and there are two disconnected complete sub-graphs K₁ and K_(n-1) which have contain 0 and ½(n-1)(n-2) edges, respectively.

Flipping the state of other vertices will disconnect each of them from the complete sub-graph containing it and connect it to all the vertices of the other complete sub-graph. So, generally, if there are x vertices that have flipped state then there will be a two complete sub-graphs K_x and K_(n-x) with ½x(x-1) and ½(n-x)(n-1-x) edges respectively for a total of m = ½n(n-1) - nx +x(x-1) edges.

If we know m and n then we can solve the quadratic equation to find the number of moves x required to solve the problem:

x = ( n - SQRT( 4m + 2n - n² ) ) / 2

If x is a non-integer then the puzzle is not solvable.

If x is an integer then the puzzle may be solvable in exactly x moves but an additional check is needed to see if there is are two disconnected complete sub-graphs K_x and K_(n-x).

Algorithm:

• Calculate x; if it is not an integer then the graph is not solvable. [Complexity: O(1)]
• Pick a random vertex:
  • its degree should be either (x-1) or (n-x-1); if it is not then the graph is not solvable.
  • generate a list of all its adjacent vertices. [Complexity: O(n)]
  • perform a depth-first (or breadth-first) search from that vertex. [Complexity: O(n+m)]
  • if the number of edges visited is ½x(x-1) or ½(n-x)(n-1-x) (corresponding to the degree of the original vertex) and no vertices are visited that were not adjacent to the original then the sub-graph is complete and you know the graph is solvable; if either condition is not true then the graph is not solvable.
• To be certain you could do the same for the other sub-graph but it is unnecessary.

Examples:

The graph where n=4,m=2 with edges (1,2) and (3,4) is solvable since x = ( 4 - SQRT( 0 ) ) / 2 = 2, an integer, and there are two K₂ disconnected sub-graphs.

The graph where n=4,m=3 with edges (1,2), (2,3), (3,4) has x = ( 4 - SQRT( 4 ) ) / 2 = 1, an integer, but there is only one, connected non-complete graph when there should be two disconnected K₁ and K₃ sub-graphs.