Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am reading a text for an upcoming class Social Network Analysis on and am trying to get a little bit ahead by reading some of the material before class starts. I am working on a question that asks me to:

Construct a graph in which all nodes are pivotal for at least one pair of nodes.

So I constructed a 'square' graph with 4 nodes A, B, C and D. The graph is undirected and is not complete, meaning there are only 4 edges between them and no diagonal edges. I am getting conflicting answers of yes and no for it being correct, I would appreciate any help, direction or readings that could be offered up.

|     |
|     |
share|cite|improve this question
up vote 2 down vote accepted

In order for a node $X$ to be pivotal for the nodes $Y$ and $Z$, $X$ must be different from $Y$ and $Z$ and must lie on every shortest path between $Y$ and $Z$. Consequently, no node in your graph is pivotal for any pair of nodes. For example, $A$ is not pivotal for $B$ and $C$ because $BDC$ is a shortest path from $B$ to $C$ that does not contain $A$.

Try a closed loop of $5$ nodes and $5$ edges instead: then each node will be pivotal for its immediate neighbors, because it will lie on the only shortest path between them.

share|cite|improve this answer
Thank you so much, I thought it was going to a fairly trivial graph, but its been a few years since I have touched graph theory unfortunately. – MCP_infiltrator Sep 10 '12 at 5:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.