Minimum Degree of a Connected Trio in a Graph

hard graph enumeration

Problem

You are given an undirected graph with n nodes (1-indexed) and an edge list. A connected trio is a set of three nodes that are all pairwise connected. The degree of a trio is the number of edges with exactly one endpoint inside the trio. Return the minimum degree of any connected trio, or −1 if there are none.

Inputn = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]

Output3

Trio {1,2,3} is the only triangle. Its degree = (deg1−2)+(deg2−2)+(deg3−2) = 1+1+1 = 3.

edges (u,v;...)

def min_trio_degree(n, edges):
    adj = [[False] * (n + 1) for _ in range(n + 1)]
    deg = [0] * (n + 1)
    for u, v in edges:
        adj[u][v] = adj[v][u] = True
        deg[u] += 1
        deg[v] += 1
    ans = float('inf')
    for a in range(1, n + 1):
        for b in range(a + 1, n + 1):
            if not adj[a][b]:
                continue
            for c in range(b + 1, n + 1):
                if adj[a][c] and adj[b][c]:
                    d = deg[a] + deg[b] + deg[c] - 6
                    ans = min(ans, d)
    return ans if ans != float('inf') else -1

function minTrioDegree(n, edges) {
  const adj = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(false));
  const deg = new Array(n + 1).fill(0);
  for (const [u, v] of edges) {
    adj[u][v] = adj[v][u] = true;
    deg[u]++; deg[v]++;
  }
  let ans = Infinity;
  for (let a = 1; a <= n; a++)
    for (let b = a + 1; b <= n; b++) {
      if (!adj[a][b]) continue;
      for (let c = b + 1; c <= n; c++)
        if (adj[a][c] && adj[b][c]) {
          const d = deg[a] + deg[b] + deg[c] - 6;
          ans = Math.min(ans, d);
        }
    }
  return ans === Infinity ? -1 : ans;
}

class Solution {
    public int minTrioDegree(int n, int[][] edges) {
        boolean[][] adj = new boolean[n + 1][n + 1];
        int[] deg = new int[n + 1];
        for (int[] e : edges) {
            adj[e[0]][e[1]] = adj[e[1]][e[0]] = true;
            deg[e[0]]++; deg[e[1]]++;
        }
        int ans = Integer.MAX_VALUE;
        for (int a = 1; a <= n; a++)
            for (int b = a + 1; b <= n; b++) {
                if (!adj[a][b]) continue;
                for (int c = b + 1; c <= n; c++)
                    if (adj[a][c] && adj[b][c]) {
                        int d = deg[a] + deg[b] + deg[c] - 6;
                        ans = Math.min(ans, d);
                    }
            }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

class Solution {
public:
    int minTrioDegree(int n, vector<vector<int>>& edges) {
        vector<vector<bool>> adj(n + 1, vector<bool>(n + 1, false));
        vector<int> deg(n + 1, 0);
        for (auto& e : edges) {
            adj[e[0]][e[1]] = adj[e[1]][e[0]] = true;
            deg[e[0]]++; deg[e[1]]++;
        }
        int ans = INT_MAX;
        for (int a = 1; a <= n; a++)
            for (int b = a + 1; b <= n; b++) {
                if (!adj[a][b]) continue;
                for (int c = b + 1; c <= n; c++)
                    if (adj[a][c] && adj[b][c]) {
                        int d = deg[a] + deg[b] + deg[c] - 6;
                        ans = min(ans, d);
                    }
            }
        return ans == INT_MAX ? -1 : ans;
    }
};

Explanation

A connected trio is just a triangle: three nodes where all three pairs share an edge. Its degree counts edges that leave the triangle — those touching exactly one of its three nodes. We want the triangle with the fewest such outgoing edges.

First we build an adjacency matrix adj for instant pair lookups and a deg array holding each node's total degree. With those two tables ready, checking a triangle and scoring it both take constant time.

We then enumerate all ordered triples a < b < c. We skip early if a and b are not connected, then confirm the triangle with adj[a][c] and adj[b][c]. Ordering the triple guarantees each triangle is examined exactly once.

For a valid triangle the outgoing degree is deg[a] + deg[b] + deg[c] - 6. The -6 removes the three internal edges, which were each double-counted (twice, once per endpoint) inside the degree sum. We keep the minimum over all triangles.

Example: edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]. The only triangle is {1,2,3} with degrees 3, 3, 3, giving 3+3+3-6 = 3. So the answer is 3.

Time: O(n³) Space: O(n²)