#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/graph-fundamentals/star-graph-the-trick

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/graph-fundamentals/star-graph-the-trick

Repovive

Star Graph - The Trick - Graph Fundamentals | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

Star Graph - The Trick

O(1) Solution

Look at Edge $1$ : [u1, v1]. Look at Edge $2$ : [u2, v2]. One of the numbers in Edge $1$ must be the center. One of the numbers in Edge $2$ must also be the center.

The center is the common node. Compare u1 with u2 and v2. If u1 equals either, return u1. Otherwise, return v1.

if u1 = u2 or u1 = v2 then
    return u1
else
    return v1

This runs in constant time regardless of graph size. Two edges are enough to identify the unique center.