I came to know a new term in Graph Theory as Graph Invariant. According to Wikipedia, a graph property or graph invariant is a property of graphs that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph.
Can anyone explain briefly what exactly graph invariants are? I am unable to grasp this concept. Thanks a lot for the help.
I think it's easier explained with a few examples.
The chromatic number of a graph is an important invariant. It is defined as the minimal number of colours you need to colour the vertices such that no neighbouring vertices have the same colour.
The degree of a graph is another invariant. It is the number of edges connected to the vertex with the fewest edges.
The number of connected components of a graph.
For a connected graph, the number of bridges (edges such that if you remove it the graph becomes disconnected).
The diameter of a graph is the distance between the two vertices which are farthest apart. The number of vertices and the number of edges. Whether the graph is Eulerian or Hamiltonian. Whether it's a planar graph.
All of these are examples of invariants: characteristics of any given graph that doesn't depend on arbitrary things like what you've named the vertices, but rather on the structure of the graph itself.
As an antiexample, @MarkS. mentioned in the comments that the number of crossings you get if you draw the graph in a plane is not an invariant, because the number of crossings depend on where exactly you put the vertices, and how you put the edges. However, the smallest possible number of crossings you can get is an invariant (I think I that this invariant is the same regardless of whether you require edges to be drawn straight).