# A measure of connectedness in graph theory

From Wikipedia:

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

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?

• Check out average clustering it's a measure of how connected a graph is. Another useful concept is density Aug 20 '18 at 14:42
• Use the number of spanning trees divided by $n^{n-2}$? Aug 20 '18 at 19:53
• 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. Aug 20 '18 at 22:26
• 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
– Mike
Aug 21 '18 at 1:06
• 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].
– Mike
Aug 21 '18 at 1:26

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.