Proof: Minimum Degree Condition for Connected Graphs | Graph Theory

Let G be a graph of order n, meaning G has n vertices. If the minimum degree of G is greater than or equal to n-1 divided by 2, then G is connected! We prove this sufficient (but not necessary) condition for a graph to be connected in today's video graph theory lesson!

I hope you find this video helpful, and be sure to ask any questions down in the comments!

+WRATH OF MATH+

Follow Wrath of Math on...

[j_travel_hobby_fun]

Thanks a ton! nowadays I just started learning competitive programming and graph theory. All of your videos about graph theory really really help me out! from Korea Thanks again

[SHASHANKRUSTAGII]

helped me in GATE CSE preparation. thanks

[xyzx]

I think it's easier to prove the contrapositive: "If G is disconnected, then the minimum degree is less than (n-1)/2".

Proof: let A and B be the vertex sets of two connected components. Suppose without loss of generality that |A|<=|B|. |A|+|B|<=n implies that |A|<=n/2. Pick v in A. v only has neighbors in A, and hence has degree at most n/2-1. Therefore the minimum degree of G is at most n/2-1, which is less than (n-1)/2.

[pandithgiri]

please explain this lemma: Let G be a nontrivial graph of order n with degree sequence
(d1, d2, . . ., dn), where d1 ≤ d2 ≤ · · · ≤ dn and n ≥ 4. Suppose that there is no integer
k < (n + 1)/2 such that dk ≤ k − 1 and dn−k+1 ≤ n − k − 1. Then G is traceable.

[sulyaniv]

is it not trivial? We know there are n(n-1)/2 edges, and n vertices. If min degree is (n-1)/2, it means at least 1 vertex is linked to the n-1 remaining vertices, making the graph connected. Or am I missing something?

[avi-ventures]

Hi WOM, I do not follow the proof's structure. In particular with the the first subproof, why does deg(u)+deg(v) >=n-1 hold. I am having troubles with structuring my proof, like which part do I prove/use for the proof as to the hypothesis. Any tips on this and the thought process would be highly appreciated.

[winminaye]

Show that if G is simple and the minimum degree is equal to half of the number of vertices in that graph, then the edge connectvity is equal to minimum degree.( may i get that problem proof)

[PunmasterSTP]

Minimum degree condition? More like "Magnificent videos; thanks for posting them!" 🙏