Claim 4.1. Let G be an undirected graph on n vertices, where n is even. If all vertices have degree at least n/2, then G
Posted: Tue Sep 07, 2021 7:21 am
- Claim 4 1 Let G Be An Undirected Graph On N Vertices Where N Is Even If All Vertices Have Degree At Least N 2 Then G 1 (26.6 KiB) Viewed 99 times
Help me plz.
Claim 4.1. Let G be an undirected graph on n vertices, where n is even. If all vertices have degree at least n/2, then G is connected. Hint: try a proof by way of contradiction. That is, assume that the claim is false-assume that G = (V. E) is an undirected graph on V = n vertices where n is even) such that all vertices have degree at least n/2, and that G is not connected. Why is this impossible? There are many ways to show such an impossibility; it might be helpful to use the "first theorem" of graph theory: Ever deg(v) = 2 E1