Thread: Construct graph with virtices

Hi,

Please help me to solve this problem?


1. Is it possible to construct a simple graph with the following condition, if not why?

a. Graph on 7 vertices having degree 5,3,3,2,2,1,0
b. 3-regular graph on 6 vertices
c. 4-regular graph on 6 vertices

a) Take a pentagon, put a 6th vertex in the middle. Connect the middle vertex to all vertices of the pentagon. Pick a vertex on the pentagon. Remove the two edges adjacent to this vertex and on the pentagon (i.e., not towards the middle vertex). Add a 7th vertex without any edges. This is your graph.

b) It is often easier to create the complementary graph. So, try creating a 2-regular graph on 6 vertices (there are 2 such graphs, up to isomorphism).

c) try the same trick as in b)

Thanks a lot.