Diameter of a Graph | Graph Theory

What is the diameter of a graph in graph theory? This is a simple term we will define with examples in today's video graph theory lesson!

Of all distances between pairs of vertices in a connected graph, the greatest distance is the diameter of the graph, written diam(G) for a graph G. In other words, the diameter of a connected graph G is the greatest distance (number of edges) necessary to travel between any pair of vertices in G.

I hope you find this video helpful, and be sure to ask any questions down in the comments!

********************************************************************
The outro music is by a favorite musician of mine named Vallow, who, upon my request, kindly gave me permission to use his music in my outros. I usually put my own music in the outros, but I love Vallow's music, and wanted to share it with those of you watching. Please check out all of his wonderful work.

********************************************************************

+WRATH OF MATH+


Follow Wrath of Math on...

[WrathofMath]

Support the production of this course by joining Wrath of Math as a Channel Member for exclusive and early videos, original music, and upcoming lecture notes for the graph theory series! Plus your comments will be highlighted for me so it is more likely I'll answer your questions!

[krishnag]

Thanks for mentioning diameter of disconnected graphs. I had hard time finding this info online. Appreciated.

[hosseinhamzeh]

I watched 25 videos of this playlist, you are awesome sir. these short videos are much better than just a full 4 hours video without any depth tutorial

[bluewhaleyshark]

Hello. Nice video. Although the definition for the diameter as the longest shortest-length path is seemingly paradoxical and confusing, it actually is the more appropriate and accurate definition than “the maximum distance between any two nodes”

For example, take a look at the graph at 06:22. The maximum distance between node a and d is actually 5, in the following sequence:
a—>f—>e—>b—>c—>d. You traverse 6 nodes, and 5 edges so the maximum distance is thus 5. And therefore the diameter should be 5. However, the answer is actually 3.

Under the definition of longest shortest-length path, you will get 3.

Out of all of the shortest-length paths in this graph or the least amount of edges traversed, the LONGEST one is from a to d:
a—>b—>c—>d which has a diameter of 3

[jsondev]

the channel i didn't know i needed, thank you for all that you do!

[LearningCS-jpcb]

People who are confused why diameter came out to be 3 and not something 4/5, please check definition of "distance"

[arrigune]

That's for undirected and unweighted graphs, isn't it? I'm looking for the same video but for the case I mention.

[ronajanefortosa]

Can you make a video about the diameter-minimal and diameter-critical graphs?

[PronteCo]

would have been a good opportunity to introduce BFS

[njudalotaibi]

Hi wrath, how about if we say the diam(G) =4 because there is path from a to d . And the distance is 4 . Like this - a b e c d .

[AdityaPatilR]

Can you say shortest distance between farthest nodes or longest distance between closest nodes?

[Medi-ysum]

Hello,
thank you very much for your intersting and usfuel videos!
I have a a question: what if I connect a to d via (a, f, e b, c and d), would the diamter be 5 in this case?

[vikramtete]

Hello Wrath...If a vertex has a loop then can we say that the loop is the path between that vertex itself? Is a loop consider as a path from a vertex v to v itself?

[iamanuj]

But what is the D(G) of a connected graph??

[lluisgimenez]

Which would be the diameter of a cycle Cn?

[dialaali]

why we did not write distance between a and d =4 by take a path (a-b-e-c-d)??

[charlessun]

Hey Sean, why don’t you talk about 3D graph theory?

[HOWTO-yutm]

hello sir, but what if i use a path from a to d like a-f-e-b-c-d. in that case the diameter getting more. is it possible or i missed sth.

[sumittete]

Sir...could you please give me an example of a complete graph containing three vertices u, v, and w such that d(uv)=d(uw)=d(vw)=diam(G)=2 ?

[pjk]

Is there a concept for a radius? I was given this question, related to diameter and radius:

"Define the radius of a graph to be the minimum over all the vertices x of max(y) distance
(x, y). Define the diameter of a graph to be the maximum distance between any two
vertices. Show for all connected graphs that the radius is less than or equal to the
diameter and that the diameter is less than or equal to twice the radius. Show an
example where the radius is equal to the diameter and another example where the
diameter is twice the radius."