Minimum degree of three nodes forming a triangle in a given Graph

0 0 8 minutes read

Given an undirected graph consisting of N vertices and M edges and an array edges[][], with each row representing two vertices connected by an edge, the task is to find the minimum degree of three nodes forming a triangle in the graph. If there doesn’t exist any triangle in the graph, then print “-1”.

Examples:

Input: N = 7, Edges = [[1, 2], [1, 3], [2, 3], [1, 4], [2, 5], [2, 7], [3, 6], [3, 7]]Output: 4
Explanation: Below is the representation of the above graph:

There are two connected triangles:

One formed by nodes {1, 2, 3}. Degree of the triangle = 5.

Second triangle formed by nodes {2, 3, 7}. Degree of the triangle = 4.

The minimum degree is 4.

Input: N = 6, Edges = [[1, 2], [1, 3], [2, 3], [1, 6], [3, 4], [4, 5]]Output: 2

Approach: The given problem can be solved by finding the degree of every triplet of nodes forming a triangle and count the degree of each node in that triangle. Follow the steps below to solve the problem:

Initialize a variable, say ans as INT_MAX that stores the minimum degree of nodes forming a triangle.
Create an adjacency matrix from the given set of edges.
Stores the degree of each node of the given graph in an auxiliary array, say degree[].
Now, iterate for all possible triplets of nodes (i, j, k) over the range [1, N] and perform the following steps:
- If there are edges between each pair of triplets, then there exists a triangle. Therefore, update the value of ans as the minimum of ans and (degree[i] + degree[j] + degree[k] – 6).
- Otherwise, continue to the next iteration.
After completing the above steps, if the value ans is INT_MAX, then print “-1”. Otherwise, print the value of ans as the minimum degree of any triangle in the graph.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum degree
// of a connected triangle in the graph
int minTrioDegree(int N,
                  vector<vector<int> >& Edges)
{
    // Store the degree of each node
    // in the graph
    int degree[N + 1] = { 0 };
 
    // Stores the representation of
    // graph in an adjancency matrix
    int adj[N + 1][N + 1] = { 0 };
 
    // Create the adjacency matrix and
    // count the degree of nodes
    for (int i = 0; i < Edges.size(); i++) {
 
        // u & v are the endpoint of
        // the ith edge
        int u = Edges[i][0];
        int v = Edges[i][1];
 
        // Mark both edges i.e.,
        // edge u->v and v->u
        adj[u][v] = adj[u][v] = 1;
 
        // Increment degree by 1
        // of both endnodes
        degree[u]++;
        degree[v]++;
    }
 
    // Stores the required result
    int ans = INT_MAX;
 
    // Traverse for the first node
    for (int i = 1; i <= N; i++) {
 
        // Traverse for the second node
        for (int j = i + 1; j <= N; j++) {
 
            // If there is an edge between
            // these two nodes
            if (adj[i][j] == 1) {
 
                // Traverse all possible
                // third nodes
                for (int k = j + 1;
                     k <= N; k++) {
 
                    // If there is an edge
                    // between third node
                    // and the previous two
                    if (adj[i][k] == 1
                        && adj[j][k] == 1) {
 
                        // Update ans
                        ans = min(ans,
                                  degree[i]
                                      + degree[j]
                                      + degree[k] - 6);
                    }
                }
            }
        }
    }
 
    // Return the result
    return ans == INT_MAX ? -1 : ans;
}
 
// Driver Code
int main()
{
    vector<vector<int> > Edges;
    Edges = { { 1, 2 }, { 1, 3 }, 
              { 2, 3 }, { 1, 4 }, 
              { 2, 5 }, { 2, 7 }, 
              { 3, 6 }, { 3, 7 } };
    int N = 7;
 
    cout << minTrioDegree(N, Edges);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the minimum degree
// of a connected triangle in the graph
static int minTrioDegree(int N,int [][]Edges)
{
    // Store the degree of each node
    // in the graph
    int degree[] = new int[N + 1];
 
    // Stores the representation of
    // graph in an adjancency matrix
    int adj[][] = new int[N + 1][N + 1];
 
    // Create the adjacency matrix and
    // count the degree of nodes
    for (int i = 0; i < Edges.length; i++) {
 
        // u & v are the endpoint of
        // the ith edge
        int u = Edges[i][0];
        int v = Edges[i][1];
 
        // Mark both edges i.e.,
        // edge u.v and v.u
        adj[u][v] = adj[u][v] = 1;
 
        // Increment degree by 1
        // of both endnodes
        degree[u]++;
        degree[v]++;
    }
 
    // Stores the required result
    int ans = Integer.MAX_VALUE;
 
    // Traverse for the first node
    for (int i = 1; i <= N; i++) {
 
        // Traverse for the second node
        for (int j = i + 1; j <= N; j++) {
 
            // If there is an edge between
            // these two nodes
            if (adj[i][j] == 1) {
 
                // Traverse all possible
                // third nodes
                for (int k = j + 1;
                     k <= N; k++) {
 
                    // If there is an edge
                    // between third node
                    // and the previous two
                    if (adj[i][k] == 1
                        && adj[j][k] == 1) {
 
                        // Update ans
                        ans = Math.min(ans,
                                  degree[i]
                                      + degree[j]
                                      + degree[k] - 6);
                    }
                }
            }
        }
    }
 
    // Return the result
    return ans == Integer.MAX_VALUE ? -1 : ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int [][]Edges = { { 1, 2 }, { 1, 3 }, 
              { 2, 3 }, { 1, 4 }, 
              { 2, 5 }, { 2, 7 }, 
              { 3, 6 }, { 3, 7 } };
    int N = 7;
 
    System.out.print(minTrioDegree(N, Edges));
 
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program for the above approach
import sys
 
# Function to find the minimum degree
# of a connected triangle in the graph
def minTrioDegree(N, Edges):
 
    # Store the degree of each node
    # in the graph
    degree = [0] * (N+1)
 
    # Stores the representation of
    # graph in an adjancency matrix
    adj = []
 
    for i in range(0, N+1):
        temp = []
        for j in range(0, N+1):
            temp.append(0)
 
        adj.append(temp)
 
    # Create the adjacency matrix and
    # count the degree of nodes
    for i in range(len(Edges)):
 
        # u & v are the endpoint of
        # the ith edge
        u = Edges[i][0]
        v = Edges[i][1]
         
        # Mark both edges i.e.,
        # edge u->v and v->u
        adj[u][v] = adj[u][v] = 1
 
        # Increment degree by 1
        # of both endnodes
        degree[u] += 1
        degree[v] += 1
 
    # Stores the required result
    ans = sys.maxsize
 
    # Traverse for the first node
    for i in range(1, N+1, 1):
 
        # Traverse for the second node
        for j in range(i + 1, N+1, 1):
 
            # If there is an edge between
            # these two nodes
            if adj[i][j] == 1:
 
                # Traverse all possible
                # third nodes
                for k in range(j + 1, N+1, 1):
 
                    # If there is an edge
                    # between third node
                    # and the previous two
                    if (adj[i][k] == 1) and (adj[j][k] == 1):
 
                        # Update ans
                        ans = min(ans, degree[i] + degree[j] + degree[k] - 6)
 
    # Return the result
    if ans == sys.maxsize:
        return -1
    return ans
 
# Driver Code
Edges = [[1, 2], [1, 3], [2, 3], [1, 4], [2, 5], [2, 7], [3, 6], [3, 7]]
N = 7
 
print(minTrioDegree(N, Edges))
 
# This code is contributed by Dharanendra L V.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
 
// Function to find the minimum degree
// of a connected triangle in the graph
static int minTrioDegree(int N, int [,]Edges)
{
   
    // Store the degree of each node
    // in the graph
    int []degree = new int[N + 1];
 
    // Stores the representation of
    // graph in an adjancency matrix
    int [,]adj = new int[N + 1, N + 1];
 
    // Create the adjacency matrix and
    // count the degree of nodes
    for (int i = 0; i < Edges.GetLength(0); i++) 
    {
 
        // u & v are the endpoint of
        // the ith edge
        int u = Edges[i, 0];
        int v = Edges[i, 1];
 
        // Mark both edges i.e.,
        // edge u.v and v.u
        adj[u, v] = adj[u, v] = 1;
 
        // Increment degree by 1
        // of both endnodes
        degree[u]++;
        degree[v]++;
    }
 
    // Stores the required result
    int ans = int.MaxValue;
 
    // Traverse for the first node
    for (int i = 1; i <= N; i++) {
 
        // Traverse for the second node
        for (int j = i + 1; j <= N; j++) {
 
            // If there is an edge between
            // these two nodes
            if (adj[i,j] == 1) {
 
                // Traverse all possible
                // third nodes
                for (int k = j + 1;
                     k <= N; k++) {
 
                    // If there is an edge
                    // between third node
                    // and the previous two
                    if (adj[i,k] == 1
                        && adj[j,k] == 1) {
 
                        // Update ans
                        ans = Math.Min(ans,
                                  degree[i]
                                      + degree[j]
                                      + degree[k] - 6);
                    }
                }
            }
        }
    }
 
    // Return the result
    return ans == int.MaxValue ? -1 : ans;
}
 
// Driver Code
public static void Main(String[] args)
{
    int [,]Edges = { { 1, 2 }, { 1, 3 }, 
              { 2, 3 }, { 1, 4 }, 
              { 2, 5 }, { 2, 7 }, 
              { 3, 6 }, { 3, 7 } };
    int N = 7;
 
    Console.Write(minTrioDegree(N, Edges));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// javascript program for the above approach
 
// Function to find the minimum degree
// of a connected triangle in the graph
function minTrioDegree(N,Edges)
{
    // Store the degree of each node
    // in the graph
    var degree = Array.from({length: N+1}, (_, i) => 0);
 
    // Stores the representation of
    // graph in an adjancency matrix
    var adj = Array(N+1).fill(0).map(x => Array(N+1).fill(0)); 
 
    // Create the adjacency matrix and
    // count the degree of nodes
    for (var i = 0; i < Edges.length; i++) {
 
        // u & v are the endpovar of
        // the ith edge
        var u = Edges[i][0];
        var v = Edges[i][1];
 
        // Mark both edges i.e.,
        // edge u.v and v.u
        adj[u][v] = adj[u][v] = 1;
 
        // Increment degree by 1
        // of both endnodes
        degree[u]++;
        degree[v]++;
    }
 
    // Stores the required result
    var ans = Number.MAX_VALUE;
 
    // Traverse for the first node
    for (var i = 1; i <= N; i++) {
 
        // Traverse for the second node
        for (var j = i + 1; j <= N; j++) {
 
            // If there is an edge between
            // these two nodes
            if (adj[i][j] == 1) {
 
                // Traverse all possible
                // third nodes
                for (var k = j + 1;
                     k <= N; k++) {
 
                    // If there is an edge
                    // between third node
                    // and the previous two
                    if (adj[i][k] == 1
                        && adj[j][k] == 1) {
 
                        // Update ans
                        ans = Math.min(ans,
                                  degree[i]
                                      + degree[j]
                                      + degree[k] - 6);
                    }
                }
            }
        }
    }
 
    // Return the result
    return ans == Number.MAX_VALUE ? -1 : ans;
}
 
// Driver Code
var Edges = [ [ 1, 2 ], [ 1, 3 ], 
              [ 2, 3 ], [ 1, 4 ], 
              [ 2, 5 ], [ 2, 7 ], 
              [ 3, 6 ], [ 3, 7 ] ];
    var N = 7;
 
    document.write(minTrioDegree(N, Edges));
 
// This code is contributed by 29AjayKumar 
</script>

Output:

Time Complexity: O(N³)
Auxiliary Space: O(N²)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!