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.
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)
How does the complexity change for a directional graph, or a directionally weighted graph? I know that digraphs are a subset of all graphs.
Possibly relevant references: