Minimum degree of a connected trio in a graph

Graph Theory Enumeration

44.3% acceptance

Feb 25, 2026

355

294

You are given an undirected graph. You are given an integer n which is the number of nodes in the graph and an array edges, where each edges[i] = [ui, vi] indicates that there is an undirected edge between ui and vi. A connected trio is a set of three nodes where there is an edge between every pair of them. The degree of a connected trio is the number of edges where one endpoint is in the trio, and the other is not. Return the minimum degree of a connected trio in the graph, or -1 if the graph has no connected trios.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_trio_degree(n: i32, edges: Vec<Vec<i32>>) -> i32 {
    let n = n as usize;
    let mut adj = vec![vec![false; n + 1]; n + 1];
    let mut deg = vec![0i32; n + 1];
    for e in &edges {
      let (u, v) = (e[0] as usize, e[1] as usize);
      adj[u][v] = true;
      adj[v][u] = true;
      deg[u] += 1;
      deg[v] += 1;
    }
    let mut ans = i32::MAX;
    for i in 1..=n {
      for j in i+1..=n {
        if !adj[i][j] { continue; }
        for k in j+1..=n {
          if adj[i][k] && adj[j][k] {
            let trio_degree = deg[i] + deg[j] + deg[k] - 6;
            ans = ans.min(trio_degree);
          }
        }
      }
    }
    if ans == i32::MAX { -1 } else { ans }
  }
}