Minimum Degree of a Connected Trio in a Graph: Triangle Detection Pattern

You are given an undirected graph with n nodes and a list of edges. A connected trio is a set of three nodes where every pair is connected by an edge (in other words, a triangle). 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 any connected trio, or -1 if no trio exists.

This is LeetCode 1761: Minimum Degree of a Connected Trio in a Graph, and it tests your ability to detect triangles efficiently and reason about graph degree calculations.

Why this problem matters

Triangle detection is a fundamental graph primitive. It shows up in social network analysis (mutual friends), clustering coefficients, and community detection. This problem adds a twist: you do not just need to find triangles, you need to evaluate each one by counting its external connections.

The naive approach of checking all triples of nodes is O(n^3), which is too slow for large graphs. The key is to use an adjacency set for O(1) edge lookups and to orient edges intelligently so you only check promising triples. This is a pattern you will see in many graph problems where brute force is too expensive and you need a smarter enumeration strategy.

The key insight

For a triangle made up of nodes i, j, and k, the degree of that trio equals the total number of edges touching any trio member, minus the internal edges. Each trio member has some degree in the full graph. If you sum degree[i] + degree[j] + degree[k], you are counting every edge connected to a trio node. But the 3 internal edges (i-j, j-k, i-k) each get counted twice in that sum (once per endpoint). So the external degree is:

trio_degree = degree[i] + degree[j] + degree[k] - 6

This formula saves you from having to iterate over all neighbors of all three nodes to count external edges. You just need the precomputed degrees.

To find triangles efficiently, iterate over each edge (u, v) and check if any node w is a neighbor of both u and v. Using an adjacency set makes that check O(1). To avoid counting each triangle three times, orient the edges: only check w values that satisfy a consistent ordering (for example, by degree or by node index).

The solution

def min_trio_degree(n, edges):
    adj = [set() for _ in range(n + 1)]
    deg = [0] * (n + 1)

    for u, v in edges:
        adj[u].add(v)
        adj[v].add(u)
        deg[u] += 1
        deg[v] += 1

    result = float('inf')

    for u, v in edges:
        if (deg[u], u) > (deg[v], v):
            u, v = v, u
        for w in adj[u]:
            if (deg[w], w) > (deg[u], u) and v in adj[w]:
                trio_deg = deg[u] + deg[v] + deg[w] - 6
                result = min(result, trio_deg)

    return result if result < float('inf') else -1

The function builds an adjacency set and degree array. For each edge (u, v), it orients the edge so u has the smaller degree (breaking ties by node index). Then it checks each neighbor w of u. If w has a higher degree than u and w is also connected to v, we have found a triangle. We compute the trio degree with the formula and track the minimum.

The ordering trick ensures each triangle is found exactly once. Without it, you would count each triangle up to six times (once for each permutation of its three nodes).

Visual walkthrough

Let's trace through a small graph to see how the algorithm finds triangles and computes their degrees.

In step 2, the trio (1, 2, 3) has nodes with degrees 3, 4, and 3. Plugging into the formula: 3 + 4 + 3 - 6 = 4. In step 3, the trio (2, 5, 6) has degrees 4, 2, and 2, giving 4 + 2 + 2 - 6 = 2. The minimum is 2.

Complexity analysis

Here m is the number of edges and n is the number of nodes.

The time complexity of O(m * sqrt(m)) comes from the degree-ordering optimization. When you orient edges from lower-degree to higher-degree nodes, each node's out-degree in the oriented graph is at most sqrt(2m). This is because if a node had out-degree greater than sqrt(2m), all its neighbors would also have degree at least that large, meaning the total number of edges would exceed m. So for each edge, the inner loop over neighbors runs at most sqrt(2m) times, giving O(m * sqrt(m)) total.

The space is O(n + m) for the adjacency sets and degree array.

The building blocks

1. Adjacency set construction

Building an adjacency set gives you O(1) edge existence checks, which is essential for triangle detection.

adj = [set() for _ in range(n + 1)]
deg = [0] * (n + 1)

for u, v in edges:
    adj[u].add(v)
    adj[v].add(u)
    deg[u] += 1
    deg[v] += 1

An adjacency list (using a list of lists) only gives O(degree) lookup for whether an edge exists. An adjacency matrix gives O(1) lookup but uses O(n^2) space. The adjacency set is the sweet spot: O(1) average lookup and O(n + m) space.

2. Triangle detection with degree ordering

The core loop iterates edges and checks for common neighbors, using degree ordering to avoid counting duplicates.

for u, v in edges:
    if (deg[u], u) > (deg[v], v):
        u, v = v, u
    for w in adj[u]:
        if (deg[w], w) > (deg[u], u) and v in adj[w]:
            trio_deg = deg[u] + deg[v] + deg[w] - 6
            result = min(result, trio_deg)

The key discipline is the ordering. By always iterating from the lower-degree endpoint and only checking higher-degree neighbors, you guarantee that each triangle (u, v, w) with deg[u] being smallest is discovered exactly once. This turns an O(n^3) brute force into O(m * sqrt(m)).

Edge cases

• No triangles: if the graph is a tree or has no cycles of length 3, return -1. The result stays at infinity.
• Single triangle: three nodes forming a complete triangle with no other edges. The degree is 0 (no external edges).
• All nodes in one triangle: n = 3 and all pairs are connected. Degree is 0.
• Multiple triangles sharing edges: a node can belong to several triangles. Each triangle is evaluated independently.
• Very dense graph: when m is close to n^2, many triangles exist. The degree-ordering optimization keeps the runtime manageable.
• Disconnected components: triangles can only exist within connected components. The algorithm handles this naturally since it iterates over edges.

From understanding to recall

You have seen how the -6 formula avoids expensive neighbor iteration and how degree ordering keeps triangle enumeration fast. The logic makes sense on paper. But when you are staring at a blank editor in an interview, can you remember to orient edges by degree, iterate neighbors of the lower-degree endpoint, and subtract 6?

Spaced repetition drills these details into muscle memory. You practice writing the adjacency set construction, the degree-oriented edge iteration, and the trio degree formula from scratch at increasing intervals. After a few rounds, you stop thinking about it. You just write it.

Related posts

• Course Schedule - Graph traversal fundamentals with adjacency lists
• Number of Provinces - Another graph problem involving connected components
• Clone Graph - Graph traversal with adjacency list construction

CodeBricks breaks this problem into its adjacency-set-construction and triangle-detection building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a triangle or graph degree problem shows up in your interview, you do not think about it. You just write it.