Construct a graph using N vertices whose shortest distance between K pair of vertices is 2 | Function to construct the simple and connected graph such that the distance between exactly K pairs of vertices is 2 ; Stores maximum possible count of edges in a graph ; Base case ; Stores edges of a graph ; Connect all vertices of pairs ( i , j ) ; Print first ( ( N - 1 ) + Max - K ) elements of edges [ ] ; Driver code
def constGraphWithCon ( N , K ) : NEW_LINE INDENT Max = ( ( N - 1 ) * ( N - 2 ) ) // 2 NEW_LINE if ( K > Max ) : NEW_LINE INDENT print ( - 1 ) NEW_LINE return NEW_LINE DEDENT ans = [ ] NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT for j in range ( i + 1 , N + 1 ) : NEW_LINE INDENT ans . append ( [ i , j ] ) NEW_LINE DEDENT DEDENT for i in range ( 0 , ( N - 1 ) + Max - K ) : NEW_LINE INDENT print ( ans [ i ] [ 0 ] , ans [ i ] [ 1 ] , sep = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 5 NEW_LINE K = 3 NEW_LINE constGraphWithCon ( N , K ) NEW_LINE DEDENT