# structural result

what exactly is the meaning of "obtaining a structural result" in mathematics, for example in graph theory?

-

## migrated from stackoverflow.comFeb 7 '11 at 4:44

This question came from our site for professional and enthusiast programmers.

I've heard of a constructive proof. Never heard of a structural result. Example? Domain? – Bill Ruppert Feb 7 '11 at 4:40
In graph theory, it usually means a result that somehow describes the structure of the graphs in question. – Arturo Magidin Feb 7 '11 at 4:52

Here is a nice structural result for general graphs.

Every graph is the disjoint union of its connected components.

Every connected graph is a tree of biconnected components. A biconnected component is one in which the removal of any one edge leaves the graph connected. An edge disconnecting the graph is known as a bridge. Removing all bridges, we get a collection of biconnected components. It's easy to see that if we shrink all biconnected components to a dot, then the original graph becomes a tree.

Every biconnected component is obtained from triconnected components (those requiring the removal of at least three edges to disconnect the graph) using two specific constructions, "series" and "parallel"; see SPQR tree for more details.

Recent results in the same vein concern the structure of claw-free graphs (Seymour and Chudnovsky) and bull-free graphs (Chudnovsky); the same method (and a lot of hard work) was used to prove the Strong Perfect Graph Theorem.

And let's not forget the Graph Minor Theorem, which is (in some sense) a vast generalization of Kuratowski's theorem.

-

There is no exact meaning of the term "structural result" across mathematics (or even across graph theory). In fact, I fear it is one of these impressive sounding terms which means very little apart from what the writer wants it to mean in any particular case (cue Humpty Dumpty and the obligatory reminder that Lewis Carroll's day job was mathematics professor). Or at least there is relatively little that it can be counted on to mean. For many mathematicians (including me) it does call something to mind, and indeed this and similar terminology appears in some of my papers and notes.

Let me to try to give an example. Consider the problem of determining whether a finite graph is planar. Perhaps the graph is given to me as an immersed planar graph, i.e., with edges crossing each other. In this case, one could ask about algorithms for making the graph planar possibly by changing the original diagram in a minimal way (in some sense). [Note that there is a game which is based upon solving this problem: planarity.] One could imagine very nice -- and certainly, very useful -- results of this kind, but somehow they are not "structural" in the sense that they are paying too much attention to the particular representation of the graph one starts with rather than its abstract structure as a graph. On the other hand, the theorem of Kuratowski-Wagner that a finite graph is planar iff it does not have $K_5$ or $K_{3,3}$ as a graph minor is more structural: it manifestly depends only on the isomorphism class of the graph.

This example is not fantastic. If I wanted to criticize it, I would start by pointing out that an immersed planar graph is a graph with additional structure of a certain kind. But I guess the idea of the nonstructuralist approach is that one does not make that additional structure explicit and try to prove theorems which mention the structure explicitly. A structuralist would say exactly what kind of metric / differential geometric object an immersed graph is, try to construct moduli spaces of such things and then study their properties, and so forth...

-
For another example with a rather different flavor, look at SPQR tree on Wikipedia. – Yuval Filmus Feb 7 '11 at 13:34
@Yuval: I had never heard of such a thing until I saw your comment, but I looked just now and it does indeed seem relevant. Perhaps you should consider parlaying your comment into an answer? – Pete L. Clark Feb 7 '11 at 14:18