Draw a graph with the given properties or if no such graph exists, explain
- simple graph with six vertices of degree $2,2,2,4,5,5$
- simple graph with 7 edges, 9 vertices each of degree at least 1.
I thought to use Handshaking Lemma to prove those but failed to apply. An undirected graph should contain an even number of vertices of odd degree. Here it holds for 1st problem. Don't know how to prove them. Help please.
2 is possible and in fact there are several ways to do it. Just add the 7 edges one by one and try to satisfy the condition as early as possible - it's difficult to go wrong.
1 is not possible. Often when working with simple graphs, if there are a lot of edges it's easier to work with the complement. The complement must have degrees $3,3,3,1,0,0$; now two vertices are irrelevant and it shouldn't be hard to see why the remaining four can't work.