Name for the number of edges we can delete so the graph is still connected

832 Views Asked by At

Let $X$ be a connected finite graph. I was wondering what is the word in English for the maximum integer $r \geq 0$ such that there exist edges $a_1, \ldots , a_r$ such that $X - a_1 - \ldots - a_r$ is connected. I would call it the "connectedness degree", but I can't find either this name or the concept itself in the internet or Hatcher's.

Edit.: Call this "connectedness degree" $c(X)$ for a connected finite graph $X$. If $\chi (X)$ is the Euler characteristic, there's a important formula (very useful to compute the fundamental group of the graph) $$\chi (X) + c(X) =1$$

1

There are 1 best solutions below

2
On

I don't think that number has a fancy name, because it is always $$ |E|-|V|+1 $$ for a connected graph. When you have removed a maximal amount of edges, what is left is a spanning tree, and the number of edges in a tree is exactly one less than the number of vertices.