# structural result

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

-
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

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

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

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.

-
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.