text: Construct a graph using N vertices whose shortest distance between K pair of vertices is 2 | C program to implement the above approach ; 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 count of edges in a graph ; Connect all vertices of pairs ( i , j ) ; Update ; Driver Code
code: #include <stdio.h> NEW_LINE void constGraphWithCon ( int N , int K ) { int Max = ( ( N - 1 ) * ( N - 2 ) ) / 2 ; if ( K > Max ) { printf ( " - 1" ) ; return ; } int count = 0 ; for ( int i = 1 ; i < N ; i ++ ) { for ( int j = i + 1 ; j <= N ; j ++ ) { printf ( " % d ▁ % d STRNEWLINE " , i , j ) ; count ++ ; if ( count == N * ( N - 1 ) / 2 - K ) break ; } if ( count == N * ( N - 1 ) / 2 - K ) break ; } } int main ( ) { int N = 5 , K = 3 ; constGraphWithCon ( N , K ) ; return 0 ; }