({{, (RefLink[GraphDiameter, paclet:ref/GraphDiameter])[g] 
gives the greatest distance between any pair of vertices in the graph g.}, {, (RefLink[GraphDiameter, paclet:ref/GraphDiameter])[{v->w,…}]
uses rules v->w to specify the graph g.}})

OpenersNotesSection(Spacer1)Details and Options

The following options can be given:

With the default setting (RefLink[EdgeWeight, paclet:ref/EdgeWeight])->(RefLink[Automatic, paclet:ref/Automatic]), the edge weight of an edge is taken to be the (RefLink[EdgeWeight, paclet:ref/EdgeWeight]) of the graph g if available; otherwise, it is 1.

Possible (RefLink[Method, paclet:ref/Method]) settings include "Dijkstra", "FloydWarshall", "Johnson", and "PseudoDiameter".

OpenersPrimaryExamplesSection(Spacer1)Examples  (13)

OpenersExampleSection0(Spacer1)Basic Examples  (1)

Give the graph diameter for a complete graph:

GraphDiameter[]

OpenersExampleSection1(Spacer1)Scope  (7)

(RefLink[GraphDiameter, paclet:ref/GraphDiameter]) works with undirected graphs:

GraphDiameter[]

Directed graphs:

GraphDiameter[]

Weighted graphs:

GraphDiameter[]

Multigraphs:

GraphDiameter[]

Mixed graphs:

GraphDiameter[]

Use rules to specify the graph:

GraphDiameter[{1->2,2->3,3->1,3->4,4->5,5->3}]

(RefLink[GraphDiameter, paclet:ref/GraphDiameter]) works with large graphs:

g=GridGraph[{10,10,10,10}];

GraphDiameter[g]//Timing

OpenersExampleSection3(Spacer1)Applications  (2)

Illustrate the diameter in two Petersen graphs:

findDiameterPath[g_?UndirectedGraphQ]:=Module[{d=GraphDistanceMatrix[g],u,v,pos},pos=First@Position[d,Max[d]];
{u,v}=Part[VertexList[g],pos];
PathGraph@FindShortestPath[g,u,v]]

HighlightGraph[#,findDiameterPath[#]]&/@{PetersenGraph[5,2],PetersenGraph[6,2]}

For a (RefLink[CompleteGraph, paclet:ref/CompleteGraph]), the diameter is 1:

HighlightGraph[#,findDiameterPath[#]]&/@Table[CompleteGraph[n,VertexSize->Small],{n,3,6}]

For a (RefLink[PathGraph, paclet:ref/PathGraph]) of size n, the diameter is n-1:

HighlightGraph[#,findDiameterPath[#]]&/@Table[PathGraph[Range[n],VertexSize->Small],{n,5,8}]

For a (RefLink[CycleGraph, paclet:ref/CycleGraph]) of size n, the diameter is (Floor[(n/2)]):

HighlightGraph[#,findDiameterPath[#]]&/@Table[CycleGraph[n,VertexSize->Small],{n,3,6}]

For a (RefLink[WheelGraph, paclet:ref/WheelGraph]) of size 5 or more, the diameter is 2:

HighlightGraph[#,findDiameterPath[#]]&/@Table[WheelGraph[n,VertexSize->Small],{n,5,8}]

A (RefLink[WheelGraph, paclet:ref/WheelGraph]) of size 4 is a complete graph, so the diameter is 1:

HighlightGraph[#,findDiameterPath[#]]&[WheelGraph[4,VertexSize->Small]]

For a (RefLink[GridGraph, paclet:ref/GridGraph]) of size {m,n}, the diameter is m+n-2:

HighlightGraph[#,findDiameterPath[#]]&/@Table[GridGraph[dim,VertexSize->Small,ImageSize->{Tiny,Tiny}],{dim,{{3,3},{3,4},{4,3},{4,4}}}]

For a (RefLink[CompleteKaryTree, paclet:ref/CompleteKaryTree]) tree of depth n, the diameter is 2 (n-1):

HighlightGraph[#,findDiameterPath[#]]&/@Table[CompleteKaryTree[n,VertexSize->Small],{n,3,5}]

Find the largest number of steps separating two people at a family gathering network:

g=ExampleData[{"NetworkGraph","FamilyGathering"}]

GraphDiameter[g]

OpenersExampleSection4(Spacer1)Properties & Relations  (3)

For a connected graph, the diameter can be computed by (RefLink[VertexEccentricity, paclet:ref/VertexEccentricity]):

g=PetersenGraph[5,2]

GraphDiameter[g]

Max[VertexEccentricity[g,#]&/@VertexList[g]]

If a simple graph has diameter greater than 3, then its complement has diameter less than 3:

g=GridGraph[{5,5}]

GraphDiameter[g]≥3

GraphDiameter[GraphComplement[g]]≤3

The graph diameter is unchanged when reversing every edge:

g=;

h=ReverseGraph[g]

{GraphDiameter[g],GraphDiameter[h]}

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[VertexEccentricity, paclet:ref/VertexEccentricity])  ▪  (RefLink[GraphRadius, paclet:ref/GraphRadius])  ▪  (RefLink[GraphPeriphery, paclet:ref/GraphPeriphery])  ▪  (RefLink[GraphCenter, paclet:ref/GraphCenter])  ▪  (RefLink[GraphDistanceMatrix, paclet:ref/GraphDistanceMatrix])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Paths, Cycles, and Flows, paclet:guide/GraphPathsCyclesAndFlows])}, {▪(RefLinkPlain[Graph Measures & Metrics, paclet:guide/GraphMeasures])}, {▪(RefLinkPlain[Graph Properties & Measurements, paclet:guide/GraphPropertiesAndMeasurements])}})}})