Graph complexity Can someone please explain briefly or direct me to some relevant tutorials/material   what we maen by complexity of a graph('graph' of graph theory) .It seems there is no one definition and that is confusing me .I would be highly obliged for any help in this regard
 A: Posting as an answer since too long for a comment

I believe different people may have different answers to this question. From this paper, 

"... complexity of a graph has been measured in several different ways. For example, the complexity of a graph has been defined to be the number of its spanning trees. It has been defined to be the value of a certain formula involving the number of vertices, edges, and proper paths in a graph. It has also been defined as the number of Boolean operations, based on a pre-determined set of Boolean operators (usually union and intersection), necessary to construct the graph from a fixed generating set of graphs".

The paper then goes on to define yet another method for measuring the complexity of a graph.
According to this article,

Computational complexity of graphs is the smallest number of union and intersection operations required to generate them when starting from simplest sets of edges: stars or cliques.

Another opinion is to use Kolmogorov Complexity to determine

how long is a minimal program to produce the graph?

I am sure there are several other points of view on this as well.
