Graph Connectivity

Question

Consider the given statements

S1: In a simple graph G with 6 vertices, if degree of each vertex is 2, then Euler circuit exists in G.

S2:In a simple graph G, if degree of each vertex is 3 then the graph G is connected.

Which of the following is/are true?

Comments

@srestha mam, if graph is having isolated vertex then it doesn't satisfy your above statement hence false. Only possible graph with 5 vertex and each of degree 2 is C5. 

---

hence first statement will be true then. right??

Only for being 6 vertices , it is incorrect. right??

---

Yupp...Your above statement is true.

Answer 1

In case of S1

G can have two triangles. As G is disconnected so it can never have Euler's circuit. So S1 is not necessarily true

[unless there are isolated vertices as components]

For S2

it is 3-regular graph but not connected. so S2 is false


PS-pardon me for the poor quality image

 

Comments

this is a snapshot from Deo graph theory book pg-23

---

@aditi19

they are telling about two triangles as an example of S1

---

oh I didn't consider that. Then it'll not have Euler circuit

thanks @srestha :)

answer updated

Answer 2

S1: Is False

Since we can make C3 C3 Means 2 cycle graph from 6 vertices. Which will be disconnected and euler cercuit will not exit.

S2 : True.

Since from 6 vertices and each having degree 3.

So only graph which is posible is complete bipartite graph (k3,3).