Graph where all nodes are pivotal I am reading a text for an upcoming class Social Network Analysis on Corsera.org 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.
A-----B
|     |
|     |
C-----D

 A: 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.
A: As @brian-m-scott mentioned already, the closed loop with 5 nodes and 5 edges work. However if you try expanding it to just 6 notes and 6 edges, you will see it doesn't work, because there are two paths for each pair of nodes on opposite ends.
To expand this to a more general case, let's consider the different graph structures. Can we have a non-cyclical graph work? No, because the end-points of such a graph would not be pivotal (ie they are not no every shortest path for two other nodes that aren't themselves) for any pair of nodes.
If the graph is cyclical, can we have edges connecting any two nodes that via the middle (aka an edge that doesn't connect two nodes that are adjacent one-another on the outer loop). I encourage you to draw out this situation. If there is an odd number of nodes and edges, and after adding one middle edge you now have an even number of edges, your sub-graph now suffers the same problem as mentioned above where you can have two paths for each pair of opposite nodes.
What if there are an even number of nodes and edges, giving an odd number of edges after adding a middle one? The answer is again no, for because there are an even number of nodes, you can still suffer the same issue as above (try it out with 10 nodes).
So you need a closed loop with odd number of nodes and odd number of edges.
