Page 1 of 1
4 True or false: graph parameters (10 points) In this problem, G is an n-vertex graph and: • 8(G) is the minimum degree
Posted: Thu May 12, 2022 6:57 am
by answerhappygod
- 4 True Or False Graph Parameters 10 Points In This Problem G Is An N Vertex Graph And 8 G Is The Minimum Degree 1 (35.11 KiB) Viewed 27 times
4 True or false: graph parameters (10 points) In this problem, G is an n-vertex graph and: • 8(G) is the minimum degree of G. • AG) is the maximum degree of G. • a(G) is the size of a largest independent set in G. • d'(G) is the size of a largest matching in G. • B(G) is the size of a smallest vertex cover in G. • w(G) is the size of a largest clique in G. Check the box next to each relationship that must hold between these quantities. 8(G) <w(G). OwG) <AG). a'(G) <BG). a(G) +w(G) = n. (G) + B(G) = n.