I'm looking for a way to measure how interconnected a graph is. It's well known that graphs can be broken down into connected components. It seems, though, that even in the cases where the graph is made of only one connected component, we can measure how interconnected that component is. Is it "almost" two components (if we would remove a small number of edges)? What is the correlation between edges (that is, if vertices A and B are each connected to C, is there a higher probability that A and B are themselves connected). I don't know how to define this measure properly, but I'm sure there are existing measures already defined.
It would seem to me that this would be a great way to measure the difficulty of an instance of the SAT problem. Representing variables as nodes and being in the same clause as edges, it would seem the difficulty of the problem is related to the interconnectedness of the graph.