Problem statement

A star graph of n nodes has one center connected to every other node by exactly one edge. Given its edge list, return the center node.

Example 1

Input: edges = [[1,2],[2,3],[4,2]]
Output: 2

Example 2

Input: edges = [[1,2],[5,1],[1,3],[1,4]]
Output: 1

Constraints

• 3 <= n <= 20
• edges.length == n - 1
• The given edges form a valid star graph.

Hints for Find Center of Star Graph

1. Hint 1

   The center appears in EVERY edge.

2. Hint 2

   Compare just the first two edges — the common endpoint is the center.

How to solve Find Center of Star Graph

In a star every edge touches the centre, and no edge joins two leaves. So the centre is the one node the edges have in common — and you only need two edges to find it. Whichever endpoint of the first edge also appears in the second must be the centre, because a leaf appears in exactly one edge.

Approach

1. Take the two endpoints a and b of edges[0].
2. Check whether a appears in edges[1].
3. If it does, a is the centre; otherwise it is b.
4. No traversal, no counting, no scan of the rest of the list.

Why it works

A star with n nodes has n - 1 edges, each connecting the centre to a distinct leaf. Every leaf therefore has degree 1 and sits in exactly one edge, while the centre sits in all of them. Since n >= 3 there are at least two edges, and the only node they can share is the centre — two distinct leaves never share an edge.

Complexity

• Time — O(1)
• Space — O(1)

Pitfalls

• Counting degrees over the whole edge list works but is O(n) for no reason — two edges settle it.
• The centre may appear as either endpoint, so check a against both entries of the second edge.
• n >= 3 guarantees a second edge exists; with only one edge the centre would be genuinely ambiguous.

Reference solution

Python

from typing import List

def findCenter(edges: List[List[int]]) -> int:
    a, b = edges[0]
    return a if a in edges[1] else b

Java

public static int findCenter(int[][] edges) {
    int a = edges[0][0];
    int b = edges[0][1];
    return (a == edges[1][0] || a == edges[1][1]) ? a : b;
}

C++

int findCenter(vector<vector<int>>& edges) {
    int a = edges[0][0];
    int b = edges[0][1];
    return (a == edges[1][0] || a == edges[1][1]) ? a : b;
}

JavaScript

var findCenter = function(edges) {
    const a = edges[0][0], b = edges[0][1];
    return (a === edges[1][0] || a === edges[1][1]) ? a : b;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More graph problems

• Find Champion II Easy
• Find Champion I Easy
• Find if Path Exists in Graph Easy
• Find the Town Judge Easy
• Minimize Maximum Component Cost Medium
• Minimum Time for K Connected Components Medium