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$ – Don Thousand 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

Your Answer

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

Browse other questions tagged or ask your own question.