Question

prove or disprove. a) If every vertex of simple graph has degree 2,then G is a cycle. b) The complement of a simple graph disconneded graph mist be connected ​

Answer 1

Answer:

a) If every vertex of a graph G has a degree at least 2, then G contains a cycle. Proof of theorem. We have already seen that if G is Eulerian, then G has at most one nontrivial component and all of the vertices of G have even degree

b) Prove that the complement of a disconnected graph is connected. We begin by assuming we have a disconnected graph G. Now consider two vertices x and y in the complement. If x and y are not adjacent in G, then they will be adjacent in G and we can find a trivial x-y path.