I've been working the past few days on adding to Wikipedia a new article on the logic of graphs. And by chance I also happened to review today this stackexchange question relating to graph toughness. That combination of events caused me to wonder: how difficult is it to express toughness as a logical sentence?

More specifically a graph is 1-tough if there is no nonempty set of vertices the removal of which would split the graph into more components than the number of removed vertices. This particular value of the toughness is relevant for the original motivation of toughness (understanding Hamiltonian cycles in the graphs) because a Hamiltonian cycle is 1-tough and a graph containing a Hamiltonian cycle is at least 1-tough.

A graph with nonzero toughness must be connected. And a connected graph \( G \) fails to be 1-tough if and only if there exists a set \( S \) of vertices that can be removed from \( G \) with the following stronger property: there is a matching between vertices of \( S \) and adjacent components of \( G-S \), in which all of the vertices of \( S \) are matched and at least one component of \( G-S \) is unmatched. For, if such a matching exists, clearly there are more components than removed vertices. And if there is any set of vertices whose removal creates too many components, let \( S \) be the smallest such set. Then either such a matching exists or (by Hall's theorem) there is a subset \( S' \) of \( S \) that is adjacent to fewer than \( |S'| \) components. Removing \( S' \) from \( S \) creates a smaller set of vertices whose removal still creates too many components, contradicting the assumed minimality of \( S \).

We can represent an adjacency between a component and one of the removed vertices by an edge connecting the component to the vertex. Using this idea we can express 1-toughness in MSO2 by a sentence that asserts the connectivity of the graph and the nonexistence of a set \( S \) of vertices and set \( A \) of edges, such that (1) each edge in \( A \) has exactly one endpoint in \( S \), (2) each vertex in \( S \) has at least one incident edge in \( A \), (3) there exists a vertex in \( S \) with more than one incident edge in \( A \), and (4) no two endpoints of edges in \( A \) are connected in \( G-S \). The connectivity tests are standard in MSO, and can be expressed in terms of the existence of a nontrivial partition of the vertices that is not crossed by any edge.

On the other hand, 1-toughness cannot be expressed in MSO1. The reason is that a complete bipartite graph with equal sides is 1-tough, a complete bipartite graph with unequal sides is not 1-tough, and MSO1 can't tell these two types of graphs apart from each other.

But this reasoning all seems very specific to 1-toughness, or at least to integer values of the toughness. Is it possible to express fractional values of toughness logically?