Code360 powered by Coding Ninjas X Code360 powered by Coding Ninjas X
Table of contents
Distance between two vertices 
Eccentricity of a vertex
Radius of connected Graph
Diameter of a Graph
Central point
Frequently Asked Questions
Key Takeaways
Last Updated: Mar 27, 2024

Properties of Graph

Author Yukti Kumari
1 upvote
Crack Google SDE interview : Essential projects
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM


Graphs are a non-linear Data Structure that is widely used in the field of computer science to solve many real-world problems. When we have many entities connected to each other somehow, our priority is to model this structure as a graph and then proceed towards a solution. Graphs are also used in social networks like Facebook and LinkedIn.


If graphs are so useful, then why not explore the subject graph theory a bit more.

In this article, we are going to study the basic properties of graphs. The properties of graphs are used to characterise them based on their structures.


Let’s see the mathematical definition of a graph before discussing about the properties of graphs - 

A graph is a set of vertices and edges G = {V, E}.




= {V,E} where,


= {a,b,c,d}

= {ab,bc,cd,da}


Following are the important properties of graph:

Distance between two vertices 

The distance between two vertices U and is defined as the number of edges present in the shortest path between and V.




We consider the shortest path between two vertices since there may exist many paths from one vertex to another.


Why not see some examples to understand - 


Consider this graph:


There are many paths between vertices and f. Some of them are as follows:


  • da → ae → ef  (length = 2)
  • dc → cg → gf   (length = 2)
  • df                      (length = 1)
  • da → ab → bc → cg → gf   (length = 4)
  • dc → cb → ba → ae → ef   (length=4)


Out of these, the shortest path is d → f.

So, the distance between d and f is 1.


Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job

Eccentricity of a vertex

Eccentricity of a vertex is defined as the maximum distance between a vertex to all the other vertices.


Notatione(V)   [eccentricity of vertex V]


In the above graph, consider the vertex ‘a’. 

Distances of all the vertices from vertex a are as follows - 















Since the maximum distance among all is 3, which is the distance between g and a, hence, the eccentricity of is 3.


      Similarly, the eccentricities of all the other vertices are as follows:

















Radius of connected Graph

Radius of a connected graph is equal to the minimum eccentricity among all the vertices. 

Notation - r(G)


For the above graph, we see that the vertex  has eccentricity=2, which is the minimum among all the eccentricities of other vertices. Hence, the radius of the graph = 2.

Diameter of a Graph

The diameter of a graph is equal to the maximum eccentricity among all the vertices.


Notation -  d(G)


For the graph above, the maximum value of eccentricity is 3. So, the diameter of the graph = 3.

Central point

The vertex whose eccentricity is equal to the radius of the connected graph is called the central point of the graph.


If r(G) = e(V), then vertex V is called the central point of the graph.


Follow up question - 

Can you tell whether a graph can have more than one central point from the above definition?


If you figured it out, then well done!!  Let’s see the answer - 

So, yes, there can be more than one central point in a graph because there can be two or more vertices having the same minimum eccentricity. 



The set of all the central points of a graph is called the centre of the graph.


Example - For the graph, we considered above, since only one vertex(vertex d) has the minimum eccentricity(here 2), so the set {‘d’} is the centre of the graph.


The circumference of a graph is said to be equal to the total number of edges in the longest cycle present in the graph.

In the above graph, the longest cycle is abcgfea, and the total number of edges is 6. So, the circumference of the graph is 6.



Girth is equal to the number of edges in the shortest cycle present in the graph.

Notation - g(G)


For the above graph, the shortest cycle has 4 edges. The shortest cycles are - abcd, eadf and fdcg. So, the girth of the graph is 4.

Also read: Application of graph data structure, hash function in data structure.

Frequently Asked Questions

  1. What is a graph?
    A graph is a non-linear data structure consisting of nodes and edges.
  2. What do you mean by the order of a graph?
    The order of a graph is equal to the number of vertices present in the graph.
  3. What is the size of a graph?
    The size of a graph is equal to the number of edges present in the graph.
  4. What is the degree of a vertex?
    The degree of a vertex is equal to the number of edges incident on the vertex.
  5. What do you mean by a connected graph?
    The graph is said to be connected if there exists a path between every pair of vertices.
  6. What is a loop in a graph?
    The edge which connects a vertex to itself is called a loop.

Key Takeaways

In this article, we discussed a topic of graph theory, i.e. basic properties of graphs. Basically, we got to know important terminologies in graphs and how they are calculated. We also saw examples to clearly understand the properties of graphs. Properties of graphs play a key role to characterise graphs and use them for different use cases.
Check out this problem - No of Spanning Trees in a Graph


If you would like to learn about graphs completely, then consider reading Graphs.

Also, check this amazing article which talks about Graph Algorithms for Competitive Programming.

Practice makes perfect! Do practice the coding questions asked in technical interviews from Coding Ninjas Studio.


Previous article
Graph Representation
Next article
A Guide to Master Graph Algorithms for Competitive Programming
Live masterclass