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
-
- Site Admin
- Posts: 899559
- Joined: Mon Aug 02, 2021 8:13 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
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