Minimum number of edges that need to be added to form a triangle | Function to return the minimum number of edges that need to be added to the given graph such that it contains at least one triangle ; adj is the adjacency matrix such that adj [ i ] [ j ] = 1 when there is an edge between i and j ; As the graph is undirected so there will be an edge between ( i , j ) and ( j , i ) ; To store the required count of edges ; For every possible vertex triplet ; If the vertices form a triangle ; If no edges are present ; If only 1 edge is required ; Two edges are required ; Driver code ; Number of nodes ; Storing the edges in a vector of pairs
def minEdges ( v , n ) : NEW_LINE INDENT adj = dict . fromkeys ( range ( n + 1 ) ) ; NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT adj [ i ] = [ 0 ] * ( n + 1 ) ; NEW_LINE DEDENT for i in range ( len ( v ) ) : NEW_LINE INDENT adj [ v [ i ] [ 0 ] ] [ v [ i ] [ 1 ] ] = 1 ; NEW_LINE adj [ v [ i ] [ 1 ] ] [ v [ i ] [ 0 ] ] = 1 ; NEW_LINE DEDENT edgesNeeded = 3 ; NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( i + 1 , n + 1 ) : NEW_LINE INDENT for k in range ( j + 1 , n + 1 ) : NEW_LINE INDENT if ( adj [ i ] [ j ] and adj [ j ] [ k ] and adj [ k ] [ i ] ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( not ( adj [ i ] [ j ] or adj [ j ] [ k ] or adj [ k ] [ i ] ) ) : NEW_LINE INDENT edgesNeeded = min ( edgesNeeded , 3 ) ; NEW_LINE DEDENT else : NEW_LINE INDENT if ( ( adj [ i ] [ j ] and adj [ j ] [ k ] ) or ( adj [ j ] [ k ] and adj [ k ] [ i ] ) or ( adj [ k ] [ i ] and adj [ i ] [ j ] ) ) : NEW_LINE INDENT edgesNeeded = 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT edgesNeeded = min ( edgesNeeded , 2 ) ; NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT return edgesNeeded ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 3 ; NEW_LINE v = [ [ 1 , 2 ] , [ 1 , 3 ] ] ; NEW_LINE print ( minEdges ( v , n ) ) ; NEW_LINE DEDENT