edges minus vertices - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T13:14:00Z http://mathoverflow.net/feeds/question/40351 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/40351/edges-minus-vertices edges minus vertices ohai 2010-09-28T17:38:12Z 2010-09-28T21:39:11Z <p>Is there a more interesting name for this graph invariant? It seems to have been called 'complexity' here <a href="http://arxiv.org/abs/math/0502579" rel="nofollow">http://arxiv.org/abs/math/0502579</a> and here <a href="http://www.mathunion.org/ICM/ICM1994.2/Main/icm1994.2.1375.1383.ocr.pdf" rel="nofollow">http://www.mathunion.org/ICM/ICM1994.2/Main/icm1994.2.1375.1383.ocr.pdf</a> .</p> <p>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.</p> http://mathoverflow.net/questions/40351/edges-minus-vertices/40355#40355 Answer by Tony Huynh for edges minus vertices Tony Huynh 2010-09-28T18:00:30Z 2010-09-28T21:39:11Z <p>As Jack Lee mentions, the related quantity $|V|-|E|$ is often called the <em>Euler characteristic</em> of the graph. I have also heard $|E|-|V|+1$ called the <em>cyclomatic number</em>. </p> http://mathoverflow.net/questions/40351/edges-minus-vertices/40358#40358 Answer by Louigi Addario-Berry for edges minus vertices Louigi Addario-Berry 2010-09-28T18:03:54Z 2010-09-28T18:03:54Z <p>My answer comes from the random graphs community. In the book <a href="http://www.amazon.ca/Random-Graphs-Svante-Janson/dp/0471175412" rel="nofollow">Random Graphs</a>, the quantity "edges minus vertices" is called the <em>excess</em>, which is quite standard terminology at least in random graphs.</p> <p>In <a href="http://arxiv.org/abs/0903.4730" rel="nofollow">these</a> <a href="http://arxiv.org/abs/0908.3629" rel="nofollow">papers</a> we call the quantity "edges minus vertices plus one" the <em>surplus</em>. In an important paper in the area, <a href="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.aop/1024404421" rel="nofollow">Aldous</a> calls edges beyond those in a spanning tree both surplus edges and excess edges. </p> http://mathoverflow.net/questions/40351/edges-minus-vertices/40369#40369 Answer by Philippe Nadeau for edges minus vertices Philippe Nadeau 2010-09-28T18:59:11Z 2010-09-28T18:59:11Z <p><em>Cyclomatic number</em> or <em>excess</em> 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.<br> Also, the number $c(G)$ occurs in algebraic graph theory as the dimension of the <a href="http://en.wikipedia.org/wiki/Cycle_space" rel="nofollow">cycle space</a> of the graph $G$.</p> http://mathoverflow.net/questions/40351/edges-minus-vertices/40375#40375 Answer by Jack Lee for edges minus vertices Jack Lee 2010-09-28T19:42:00Z 2010-09-28T19:59:40Z <p>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 <em>Euler characteristic</em> $\chi(G)$ is defined as the alternating sum (#0-cells)-(#1-cells)+(#2-cells)-... (see <a href="http://en.wikipedia.org/wiki/Euler_characteristic" rel="nofollow">Wikipedia</a>). 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.</p> <p>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 <em>cyclomatic number</em> or the <em>circuit rank</em> (see <a href="http://mathworld.wolfram.com/CircuitRank.html" rel="nofollow">Mathworld</a>). But if the graph is not connected, then "$+1$" must be replaced by "$+k$," where $k$ is the number of components.</p>