From Wikipedia:

A complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.

Complete graph

A tree is an undirected graph in which any two vertices are connected by exactly one path.


To me, these two types of graphs seem like some kind of opposites in terms of connectivity. I have been searching online for a graph property that reflects this difference, like Wiener index, circuit rank, strength, etc.

I couldn't find a property that measures the thing I desire: something like an averaged number that defines a node's connectivity to more than 1 node. A normalized value that should be minimum for a tree e.g. ~0 and maximum for a complete graph e.g. ~1.

Does such a measure exist in literature?

  • 1
    $\begingroup$ Check out average clustering it's a measure of how connected a graph is. Another useful concept is density $\endgroup$ Aug 20 '18 at 14:42
  • 1
    $\begingroup$ Use the number of spanning trees divided by $n^{n-2}$? $\endgroup$
    – Somos
    Aug 20 '18 at 19:53
  • 1
    $\begingroup$ If we require the graphs be connected, a graph of $n$ vertices has between $n-1$ and $\binom{n}{2}$ edges. These endpoints are necessarily trees and complete graphs respectively. Counting the edges could thus provide a very simple measure. $\endgroup$
    – Kajelad
    Aug 20 '18 at 22:26
  • 2
    $\begingroup$ Well but there are a lot of measures of connectedness though that have been the focus of research. There are plenty of papers in the literature that study the bisection width, and $\frac{|E(S,|\bar{S})|}{\min\{|S|,|\bar{S}| \}}$, as well as more basic $k$-connectedness $\endgroup$
    – Mike
    Aug 21 '18 at 1:06
  • 1
    $\begingroup$ There is even a whole stream of many many papers devoted to the construction of expander graphs, which are sparse graphs that are highly connected [if you want to find a balanced cut of an expander $G$ you need to cut a large fraction of the edges and/or vertices]. $\endgroup$
    – Mike
    Aug 21 '18 at 1:26

Some relevant metrics are described here. First, there is the connectivity, which describes the number of vertices you need to remove to make the graph disconnected. In the case of a tree with 3 or more vertices, this is 1. In the case of a complete graph, it is V. And in a disconnected graph it's 0, so it's easy to normalize. A similar property holds if you replace the number of vertices to remove with the number of edges to remove.

A metric which is a bit more of a global property is the average connectivity, given by computing the minimum number of edges between any two vertices $\kappa(u, v)$ that you need to remove to cause the graph to be disconnected and averages over all pairs: $$\frac{\sum_{u\neq v\in V}\kappa(u,v)}{\binom{|V|}{2}}.$$ The first source also defines an analogous vertex connectivity, though I don't understand their definition for vertex connectivity when $u$ and $v$ are adjacent.

Another idea I think could be interesting, but I don't know that anyone has ever really researched is the expected number of edges/vertices that need to be removed to disconnect the graph, if you choose randomly.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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