3 When We Take The Union Of Graphs With The Same Vertex Set We Just Keep That Set Of Vertices And Include An Edge If I 1 (22.37 KiB) Viewed 29 times
3 When We Take The Union Of Graphs With The Same Vertex Set We Just Keep That Set Of Vertices And Include An Edge If I 2 (22.37 KiB) Viewed 29 times
3. When we take the union of graphs with the same vertex set, we just keep that set of vertices and include an edge if it is contained in any of the graphs. (a) Prove that if G is the union of k forests, then the minimum degree of G is 2k - 1 or less. (Think about the proof of Lemma 3.1.) (b) Prove that if G is the union of k forests, then it is 2k-colorable. (e) Prove that the complete graph Kzx is the union of k forests, so we can't prove any better result than what we got in part (b).
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!