Skip to content
Free public beta until December 4, 2026: every course is open, no card needed. After that, the first chapter of each course stays free and full access is a one-time $39 ($19 for up to 100 founding members chosen for helpful feedback). Your progress is kept. How the beta works

Recipe

Find the center of a graph

Use when: you have a connected graph and need every vertex whose eccentricity is the smallest possible, not just the radius number itself

Goal: the exact set center(G): one vertex, several tied together, or the entire graph

Taught in The center of a graph

Quick recipe

  1. Get every vertex's eccentricity
  2. Find the radius
  3. Collect every vertex tied for that minimum
  1. 1

    Run Section 6's recipe first: BFS from every vertex and record each one's eccentricity. The center is defined directly from this same list, so nothing below can start without it.

    Example

    On the two-triangles graph (edges A\text{-}B, A\text{-}C, B\text{-}C, C\text{-}D, C\text{-}E, D\text{-}E), Section 6 already found \operatorname{ecc}(A)=\operatorname{ecc}(B)=\operatorname{ecc}(D)=\operatorname{ecc}(E)=2 and \operatorname{ecc}(C)=1.

    Why: the center is defined entirely in terms of eccentricity and radius, so both have to exist before the definition can even be applied.

  2. 2

    Scan the eccentricity list for its smallest value -- that's the radius, exactly as Section 6 defined it.

    Example

    The smallest entry in \{2,2,1,2,2\} is 1, so \operatorname{rad}(G)=1.

    Why: the center is defined as "eccentricity equals the radius," so the radius has to be pinned down before anything can be compared to it.

  3. 3

    Go back through the whole list and mark every vertex whose eccentricity equals the radius, not just the first one that matches.

    Example

    Only C has eccentricity 1; A,B,D,E all have eccentricity 2 \neq 1, so \operatorname{center}(G)=\{C\}.

    • exactly one vertex achieves the radius — the center is that single vertex.
    • two or more vertices tie for the radius — the center contains every one of them, not just the first found.
    • every vertex achieves the radius — the graph is self-centered, and \operatorname{center}(G) = V(G).

    ⚡ Shortcut

    If the graph is a tree, the center is guaranteed to have exactly 1 or 2 vertices, never more (Chapter 3 proves why). Finding one or two tied vertices there confirms the count instead of leaving it in question.

    Why: the definition names the whole set of eccentricity-equals-radius vertices as the center, so a tie is never resolved by picking just one.

Common mistakes

  • Reporting only one vertex when several vertices actually tie for the minimum eccentricity.
  • Confusing the center (a set of vertices) with the radius (a single number) -- they come from the same list but answer different questions.
  • Guessing the center from the drawing's visual middle instead of the actual eccentricity numbers.
  • Forgetting to recheck every eccentricity after the graph changes, since an old center can go stale the moment an edge is added or removed.