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:
“There are ... two minimum conditions necessary and sufficient for the existence of a legal system. On the one hand those rules of behavior which are valid according to the system’s ultimate criteria of validity must be generally obeyed, and on the other hand, its rules of recognition specifying the criteria of legal validity and its rules of change and adjudication must be effectively accepted as common public standards of official behavior by its officials.”
—H.L.A. (Herbert Lionel Adolphus)
“There is always a degree of ridicule that attends a disappointment, though often very unjustly, if the expectation was reasonably grounded; however, it is certainly most prudent not to communicate, prematurely, one’s hopes or one’s fears.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“What is Americanism? Every one has a different answer. Some people say it is never to submit to the dictation of a King. Others say Americanism is the pride of liberty and the defence of an insult to the flag with their gore. When some half-developed person tramples on that flag, we should be ready to pour out the blood of the nation, they say. But do we not sit in silence when that flag waves over living conditions which should be an insult to all patriotism?”
—Anna Howard Shaw (1847–1919)