Eccentricities of Adjacent Vertices Differ by at Most 1 | Graph Theory

We prove if two vertices are adjacent, their eccentricities differ by at most 1! This result follows pretty easily from the definition of vertex eccentricity of a vertex v in a graph G, that it is the maximum distance between v and vertex of G. Explained differently, there is some vertex of G furthest from v, and the distance between v and that furthest vertex is the eccentricity of v. Note that for this proof, because we are considering finite distances involving all vertices of a graph, we are assuming we have a connected graph.

Roughly speaking, this result is true because if u and v are adjacent vertices, we can always travel from u to a vertex x by going to v, then traveling along the path from v to x, and similarly to go from v to x we can travel to u then along the path from u to x. Point being that the distance between u and a vertex differs from the distance between v and a vertex by no more than 1.

#GraphTheory #Math

★DONATE★

Thanks to Robert Rennie and Barbara Sharrock for their generous support on Patreon!

Follow Wrath of Math on...

[WrathofMath]

Hundreds more graph theory videos still to come!

[gradientO]

Thanks. Graph theory is very important in computer science

[kage-musha]

amazing, just by seeing the problem title, i was able to prove this :D thanks alot sir, i have completed your entire playlist the only thing missing here it about,
Symmetric difference in graph

[rdritoch]

Thanks for creating this series, you took a very academic branch of math and made it entertaining! I can't think of many practical problems that this knowledge could be applied to but my interest peaked when you presented the matrix representation. I was disappointed it ended with that. Are there more practical applications of Graph theory using their matrix representation or is this all the graph theory knowledge that currently exists? Also it would be great if you had some videos on Tensor calculus, specifically the Christoffel symbol. No matter how many times I study it, I just can't visualize what it does.

[maheshpatel]

I dont know why I am watching this though I am in class 12! I know eccentricity of ellipse and that all stuff. Dont mind. Are you American?

[mariamaria-dohe]

thanks bro, please sean could you make a video about "directed graph" (representation of the graphe, representation of the matrixe 'incidence and adjacence', the successor table....etc), thanks a lot god bless you ♥ and I'm sorry for my bad english

[PunmasterSTP]

Adjacent vertices? More like "Amazing videos; thanks for these!" 🙏

(Also, hopefully at least a few people find my eccentric comments to be entertaining.)