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

same can be done for s1...its also 2-regular having 2 components

---

S1 need not to be always true. As @sandygate said above, there can be a graph with 2 components each of 3 vertices connected as a cycle. Nothing is mentioned graph is connected or not hence it is not always true.

---

@aditi19 how s1 will be true?

consider a graph with 2 components each of 3 vertices connected as a cycle. then s1 will false.

---

@aditi19

and

@Gyanu

eular circuit or graph can be disconnected

chk it https://math.stackexchange.com/questions/1414667/is-it-possible-disconnected-graph-has-euler-circuit

---

@srestha

I want to know 1 thing

if Eulerian graph is disconnected the how can you traverse all the edges if there are components?

and yes Eulerian graph can be disconnected in a special case. Only one component has all the edges and the remaining components are isolated vertices

---

@aditi19

yes, that is true.

Still according to wiki, disconnected eular graph possible, if (n-1) component has isolated vertex.

right??

See 1st statement will be true if we just change one number in it

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

It will be true , right??

---

if degree of each vertex is 2 then how can isolated vertex exist?

degree of isolated vertex is 0

---

yes, but how do u  confirm , it always need to be isolated vertex?

---

sorry didn't get u?

---

 Only one component has all the edges and the remaining components are isolated vertices

how r u confirming this??

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

is this statement true? 

---

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).