6
$\begingroup$

Is there a more interesting name for this graph invariant: edges minus vertices? It seems to have been called 'complexity' in

  • Remco van der Hofstad, Joel Spencer, Counting Connected Graphs Asymptotically, European Journal of Combinatorics 27 Issue 8 (2006) 1294–1320, doi:10.1016/j.ejc.2006.05.006, arXiv:math/0502579

and in

The motivation is that we want to talk about a quantity that is preserved under the graph transformation of collapsing two distinct vertices connected by an edge to a single vertex (thereby removing one edge and one vertex, preserving 'edges minus vertices'). So for example if the quantity 'edges minus vertices plus one' is more natural for some reason and has a name, then this would also be helpful. The concept should not be restricted to e.g. planar graphs.

$\endgroup$
9
  • 3
    $\begingroup$ Euler characteristic: it is the Euler characteristic of the one dimensional simplicial complex associated to the graph. $\endgroup$
    – damiano
    Sep 28, 2010 at 17:56
  • 1
    $\begingroup$ I guess I meant a multigraph or something instead of a graph. For example if I have three vertices and three edges connected triangle-style, then after I 'collapse' one of the edges I would want the new graph (or multigraph I guess) to consist of two vertices which are connected to each other by two edges. $\endgroup$
    – ohai
    Sep 28, 2010 at 18:02
  • 1
    $\begingroup$ If you contract a loop, you lose one edge and no vertices. $\endgroup$
    – Tony Huynh
    Sep 28, 2010 at 18:24
  • 1
    $\begingroup$ The transformation does not contract loops; by 'two vertices connected by an edge' I meant two distinct vertices. $\endgroup$
    – ohai
    Sep 28, 2010 at 18:26
  • 1
    $\begingroup$ Ohai, the Euler characteristic is a homotopy invariant of topological spaces, and edge contraction is a homotopy equivalence. (OK, you can get what you want without getting into these technicalities, but this is the topological point of view.) $\endgroup$
    – HJRW
    Sep 28, 2010 at 19:39

4 Answers 4

13
$\begingroup$

Whether you're considering a multigraph (which may have multiple edges and/or loops) or a simple graph, both are CW complexes. For any finite CW complex $G$, the Euler characteristic $\chi(G)$ is defined as the alternating sum (#0-cells)-(#1-cells)+(#2-cells)-... (see Wikipedia). Thus for a finite graph, the Euler characteristic is $|V|-|E|$. It's a homotopy invariant, and the operation of collapsing one edge and its vertices to a single vertex is a homotopy equivalence, so any function of $|V|-|E|$ is invariant under this operation.

When the graph is connected, the quantity $|E|-|V|+1$ ($=1-\chi(G)$) is the smallest number of edges that must be removed to yield a graph with no cycles, called the cyclomatic number or the circuit rank (see Mathworld). But if the graph is not connected, then "$+1$" must be replaced by "$+k$," where $k$ is the number of components.

$\endgroup$
1
5
$\begingroup$

Cyclomatic number or excess are indeed common names for the quantity $|E|-|V|+1$ (as other answers mention). Let me add that the correct quantity to consider when you have $k$ components in your graph $G$ is $c(G):=|E|-|V|+k$. Then $c(G)=0$ means exactly that $G$ is a forest.
Also, the number $c(G)$ occurs in algebraic graph theory as the dimension of the cycle space of the graph $G$.

$\endgroup$
1
$\begingroup$

As Jack Lee mentions, the related quantity $|V|-|E|$ is often called the Euler characteristic of the graph. I have also heard $|E|-|V|+1$ called the cyclomatic number.

$\endgroup$
1
  • 1
    $\begingroup$ @Tony: Actually, the Euler characteristic is $|V|-|E|$. See my answer. $\endgroup$
    – Jack Lee
    Sep 28, 2010 at 19:32
1
$\begingroup$

My answer comes from the random graphs community. In the book Random Graphs, the quantity "edges minus vertices" is called the excess, which is quite standard terminology at least in random graphs.

In these papers we call the quantity "edges minus vertices plus one" the surplus. In an important paper in the area, Aldous calls edges beyond those in a spanning tree both surplus edges and excess edges.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.