Find Center of Star Graph: Graph Observation Pattern

You are given a star graph with n nodes labeled 1 through n. A star graph has one center node connected to every other node, and no other edges. You are given a 2D array edges where each edges[i] = [u, v] indicates an edge between nodes u and v. Return the center of the star graph.

This is LeetCode 1791: Find Center of Star Graph, and it is a great example of how understanding the structure of a graph can reduce a problem to a single observation. No traversal, no adjacency list, no BFS or DFS. Just look at the data and read off the answer.

Why this problem matters

Find Center of Star Graph teaches you to pause and think before you code. Your first instinct might be to build an adjacency list, count degrees, and find the node with the highest degree. That works, but it is O(n) time and O(n) space, and it completely misses the point.

The real lesson here is that graph problems sometimes have structural shortcuts. A star graph has a very specific shape: one hub connected to everything else. That shape constrains the answer so tightly that you can identify the center by looking at just two edges. Once you see this, the code writes itself in three lines.

This kind of "observation before algorithm" thinking shows up constantly in interviews. Interviewers want to see that you can recognize when a problem is simpler than it looks, rather than jumping to a general-purpose algorithm. The habit of asking "what does the structure guarantee?" before writing code will save you time on easy problems and unlock insights on harder ones.

The key insight

In a star graph, every single edge connects to the center node. There are no edges between outer nodes. This means the center node appears in every edge in the list.

If the center appears in every edge, it definitely appears in the first two edges. So you just need to find the node that is common to edges[0] and edges[1]. Check if edges[0][0] appears in edges[1]. If it does, that is the center. If it does not, then edges[0][1] must be the center.

Two comparisons. Done.

The solution

def find_center(edges: list[list[int]]) -> int:
    if edges[0][0] == edges[1][0] or edges[0][0] == edges[1][1]:
        return edges[0][0]
    return edges[0][1]

The function grabs the first element of the first edge, edges[0][0], and checks whether it also appears in the second edge. If edges[0][0] matches either edges[1][0] or edges[1][1], then it is the common node and therefore the center. Otherwise, edges[0][1] is the one that appears in both edges, so we return that.

This works because the center is guaranteed to exist and to be unique. The problem statement tells us the graph is a valid star graph, so exactly one node connects to all others. That node must appear in every edge, so checking just two edges is sufficient to identify it.

Visual walkthrough

Let's trace through the example with edges = [[1,2],[2,3],[2,4],[2,5]]. We only need the first two edges.

The algorithm never touches edges beyond the first two. No matter how large the star graph is, the answer comes from comparing four numbers.

Complexity analysis

Time is O(1). We perform at most two comparisons, regardless of how many edges or nodes the graph has. We never iterate through the edge list.

Space is O(1). We do not allocate any data structures. The function reads values directly from the input array and returns a number.

The building blocks

1. Structural observation in graphs

The core technique here is recognizing what a graph's structure guarantees about its edge list. In a star graph, the center appears in every edge. In a tree, there is exactly one path between any two nodes. In a DAG, there are no cycles. Each of these structural facts can simplify algorithms dramatically.

if edges[0][0] == edges[1][0] or edges[0][0] == edges[1][1]:
    return edges[0][0]
return edges[0][1]

Before reaching for BFS or DFS, ask yourself: "What does the structure guarantee? Can I read the answer off the input directly?"

2. Degree counting as a fallback

When the structural shortcut is not obvious, degree counting is a reliable general approach for star graph problems. Count how many edges each node participates in. The center will have degree n-1.

from collections import Counter

def find_center_general(edges: list[list[int]]) -> int:
    degree = Counter()
    for u, v in edges:
        degree[u] += 1
        degree[v] += 1
    return max(degree, key=degree.get)

This runs in O(n) time and O(n) space. It is the approach you would use if the problem did not guarantee a star graph, or if you needed to verify that the graph is actually a star. Knowing both the O(1) shortcut and the general fallback shows an interviewer that you understand the problem deeply.

Edge cases

• Minimum star graph (n=3, two edges): the smallest possible star. The two-edge check works perfectly since there are exactly two edges.
• Large n: the algorithm is still O(1). Even with millions of edges, you only look at the first two.
• Center is edges[0][0]: the first branch of the if-statement returns immediately.
• Center is edges[0][1]: the if-check fails, and we fall through to return edges[0][1].
• Edge order varies: the center might be listed first or second in each edge. The check handles both positions by comparing against edges[1][0] and edges[1][1].

From understanding to recall

You have seen that Find Center of Star Graph is really about one observation: the center appears in every edge, so look at the first two edges and find the common node. The code is three lines. The logic is clean.

But under interview pressure, even simple problems can trip you up. Did you check edges[0][0] against both positions in edges[1]? Did you handle the fallback case? These tiny details are the difference between solving a problem in 30 seconds and debugging for five minutes. Spaced repetition builds the muscle memory so that the correct pattern comes out automatically, even when you are nervous.

Related posts

• Clone Graph - Classic graph traversal using BFS with a hash map to track visited nodes
• Number of Islands - Grid-based graph exploration using DFS flood fill
• Course Schedule - Graph traversal with topological ordering using in-degree counting

CodeBricks breaks Find Center of Star Graph into its observation and degree-counting building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a graph observation problem shows up in your interview, you do not hesitate. You just write it.