The number of different graphs obtained from the given graph by removing an edge.

The minimal number of edges to add or remove to make a graph edge transitive. A graph is edge transitive, if for any two edges, there is an automorphism that maps one edge to the other.

The number of edges minus the number of vertices plus 2 of a graph. When G is connected and planar, this is also the number of its faces. When $G=(V,E)$ is a connected graph, this is its $k$-monochromatic index for $k>2$: for $2\leq k\leq |V|$, the $k$-monochromatic index of $G$ is the maximum number of edge colors allowed such that for each set $S$ of $k$ vertices, there exists a monochromatic tree in $G$ which contains all vertices from $S$. It is shown in [1] that for $k>2$, this is given by this statistic.

The cutwidth of a graph. This is the minimum possible width of a linear ordering of its vertices, where the width of an ordering $\sigma$ is the maximum, among all the prefixes of $\sigma$, of the number of edges that have exactly one vertex in a prefix.

The normalized isoperimetric number of a graph. The isoperimetric number, or Cheeger constant, of a graph $G$ is $$i(G) = \min\left\{\frac{|\partial A|}{|A|}\ : \ A\subseteq V(G), 0 < |A|\leq |V(G)|/2\right\},$$ where $$\partial A := \{(x, y)\in E(G)\ : \ x\in A, y\in V(G)\setminus A \}.$$ This statistic is $i(G)\cdot\lfloor n/2\rfloor$.

The maximum cut size of a graph. A '''cut''' is a set of edges which connect different sides of a vertex partition $V = A \sqcup B$.

The skewness of a graph. For a graph $G$, the '''skewness''' of $G$ is the minimum number of edges of $G$ whose removal results in a planar graph.

The minimal crossing number of a graph. A '''drawing''' of a graph $G$ is a drawing in $\mathbb{R}^2$ such that * the vertices of $G$ are distinct points, * the edges of $G$ are simple curves joining their endpoints, * no edge passes through a vertex, and * no three edges cross in a common point. The '''minimal crossing number''' of $G$ is then the minimal number of crossings of edges in a drawing of $G$. In particular, a graph is planar if and only if its minimal crossing number is $0$. It is moreover conjectured that the crossing number of the complete graph $K_n$ [1] is $$\frac{1}{4}\lfloor \frac{n}{2} \rfloor\lfloor \frac{n-1}{2} \rfloor\lfloor \frac{n-2}{2} \rfloor\lfloor \frac{n-3}{2} \rfloor,$$ and the crossing number of the complete bipartite graph $K_{n,m}$ [2] is $$\lfloor \frac{n}{2} \rfloor\lfloor \frac{n-1}{2} \rfloor\lfloor \frac{m}{2} \rfloor\lfloor \frac{m-1}{2} \rfloor.$$ A general algorithm to compute the crossing number is e.g. given in [3]. This statistics data was provided by Markus Chimani [6].