Minimum Degree Conditions
The preceding theorems give conditions for a small object to appear within a (perhaps) very large graph. At the opposite extreme, one might search for conditions which force the existence of a structure which covers every vertex. But it is possible for a graph with
edges to have an isolated vertex - even though almost every possible edge is present in the graph - which means that even a graph with very high density may have no interesting structure covering every vertex. Simple edge counting conditions, which give no indication as to how the edges in the graph are distributed, thus often tend to give uninteresting results for very large structures. Instead, we introduce the concept of minimum degree. The minimum degree of a graph G is defined to be
Specifying a large minimum degree removes the objection that there may be a few 'pathological' vertices; if the minimum degree of a graph G is 1, for example, then there can be no isolated vertices (even though G may have very few edges).
A classic result is Dirac's theorem, which states that every graph G with n vertices and minimum degree at least n/2 contains a Hamilton cycle.
Read more about this topic: Extremal Graph Theory
Famous quotes containing the words minimum, degree and/or conditions:
“After decades of unappreciated drudgery, American women just don’t do housework any more—that is, beyond the minimum that is required in order to clear a path from the bedroom to the front door so they can get off to work in the mourning.”
—Barbara Ehrenreich (20th century)
“Essential truth, the truth of the intellectualists, the truth with no one thinking it, is like the coat that fits tho no one has ever tried it on, like the music that no ear has listened to. It is less real, not more real, than the verified article; and to attribute a superior degree of glory to it seems little more than a piece of perverse abstraction-worship.”
—William James (1842–1910)
“Purity is not imposed upon us as though it were a kind of punishment, it is one of those mysterious but obvious conditions of that supernatural knowledge of ourselves in the Divine, which we speak of as faith. Impurity does not destroy this knowledge, it slays our need for it.”
—Georges Bernanos (1888–1948)