Background:
There are 5 ways to represent a mathematical idea: words/text, tables of numbers, plots/figure, symbolic expressions, flowcharts/graph.
When I ask about "graphs" (below) I do not mean a picture of the relationship of x-vs-y (aka plot), but I do mean the nodes-and-edges, graph-theory version. I also presume that the graph is connected - there is not any node such that by traversing edges it is impossible to get from that node to any other node in the graph.
Within the words/text there is the idea of cyclomatic complexity for a program.
Within the symbolic expressions we can look at count of operators and count of parameters to get an idea of complexity of an expression.
Question:
What are some ways to measure the complexity of a graph? Is is an expression comprised of edges and nodes? Is there a single number? I would think there are an infinite variety, but I'm not sure how to grapple with this one.
Example random metric:
How long it takes in step-count, on average, over many trials, with random starting position, for a random graph walker to touch every edge and every node? Is that a thing? (I just thought of this, and it is a thing. 1, 2)
Follow-up question:
How does the complexity change for a directional graph, or a directionally weighted graph? I know that digraphs are a subset of all graphs.
Update:
Possibly relevant references: