The Gateway to Computer Science Excellence

+2 votes

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?

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?

+1

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

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

0

@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

0

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

0

@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

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

0

eular graph can be disconnected.

right??

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

0

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

0

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

0

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

0

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

0

0

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

What about self dual graph??

What about self dual graph??

0

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.

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

0

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?

0

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

0

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

+2 votes

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

+1

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.

0

@aditi19 how s1 will be true?

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

0

and

eular circuit or graph can be disconnected

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

0

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

0

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??

52,218 questions

59,890 answers

201,084 comments

118,128 users