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

both true

---

srestha mam ... second one not true i think.

we dont know how many vertices

---

could you please explain how S2 is true?

---

yes sorry 2nd one not true

---

can anyone tell me how 1 is correct...let us consider we have 6 vertices. now if we divide the 6 vertices into 2 set of 3 vertices each. then we can have 2 cycles or two components. in this case eular circuit is not present. i think for a graph to be eular, the graph must have even degree for each vertex and it must be connected.

hence both must be wrong. correct me if anything is wrong

---

@sandygate we have a theorem for euler circuit

if the vertices of a connected multigraph all have even degree, then the

graph has an Euler circuit.

so first one is true

---

but in option connected is not mentioned so we dont know if the graph is connected or not. hence first is false

---

@sandygate

it is connected because

no of edges in this graph would be (6*2/2)= 6

by handshaking lemma

with 6 edges and with 2 degree of each vertex it is nothing but cycle with 6 nodes

hence it is connected also with even number degree their exist Euler circuit

---

i dont think so we can have 2 triangles

---

oh i missed this point thanks then you are right

it will not always true

---

that's why both must be wrong

---

@sandygate u r correct. both s1 and s2 are false.

---

@Gyanu

eular graph can be disconnected.

right??

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

---

@srestha mam, in graph theory book by Narsingh Deo, statement given- "an Euler graph is always connected, except for any isolated vertices the graph may have. Since isolated vertices do not contribute anything to the understand of euler graph, it is hereafter assume that Euler graph do not have any isolated vertices and therefore connected."(sec. 2-6) 

---

wikipedia says

"An Eulerian graph is one in which all vertices have even degree; Eulerian graphs may be disconnected. For planar graphs, the properties of being bipartite and Eulerian are dual: a planar graph is bipartite if and only if its dual graph is Eulerian."

So, a graph and it's dual can be disconnected.

right??

https://en.wikipedia.org/wiki/Bipartite_matroid#Duality_with_Eulerian_matroids

---

@srestha mam, I think Euler graph may be disconnected if one connected component have all vertices of even degree and other components have isolated vertices(no edges in other components). 

Correct me if I'm wrong. 

---

@srestha mam, I think Euler graph may be disconnected if one connected component have all vertices of even degree and other components have isolated vertices(no edges in other components). 

Correct me if I'm wrong. 

---

@srestha mam, I think Euler graph may be disconnected if one connected component have all vertices of even degree and other components have isolated vertices(no edges in other components). Correct me if I'm wrong. 

---

but it is not written specifically, that one of them need to be always isolated. right??

What about self dual graph??

---

It's not written thts why S1 should be false.

Self-Dual graph:- If a planar graph is isomorphic to its own dual, it is called a self dual graph.

---

@Gyanu

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

Then what will be ur answer?

---

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

---

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