Page 1 of 1
3. (1.5 marks) Recall the following statement from Worksheet 11: Theorem 1. If G = (V, E) is a simple graph (no loops or
Posted: Fri May 20, 2022 10:09 am
by answerhappygod
- 3 1 5 Marks Recall The Following Statement From Worksheet 11 Theorem 1 If G V E Is A Simple Graph No Loops Or 1 (104.55 KiB) Viewed 34 times
3. (1.5 marks) Recall the following
statement from Worksheet 11: Theorem 1. If G = (V, E) is a simple graph (no loops or multi-edges) with VI = n > 3 vertices, and each pair of vertices a, b € V with a, b distinct and non-adjacent satisfies deg(a) + deg(b) > n, then G has a Hamilton cycle. (a) Using this fact, or otherwise, prove or disprove: Every connected undirected graph having degree sequence 2, 2, 4, 4,6 has a Hamilton cycle. (b) The
statement: Every connected undirected graph having degree sequence 2, 2, 4, 4,6 has a Hamilton cycle A. True B. False