+1 vote
217 views
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?
| 217 views
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

@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
but it is not written specifically, that one of them need to be always isolated. right??

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

@Gyanu

If the question is "In a simple graph G with 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.

0
hence first statement will be true then. right??

Only for being 6 vertices , it is incorrect. right??
0
Yupp...Your above statement is true.

+1 vote

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

by Active (4.9k points)
edited by
0
same can be done for s1...its also 2-regular having 2 components
+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

@Gyanu

eular circuit or graph can be disconnected

0

@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

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 vertices, if degree of each vertex is 2, then Euler circuit exists in G."

It will be true , right??

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

degree of isolated vertex is 0
0
yes, but how do u  confirm , it always need to be isolated vertex?
0
sorry didn't get u?
0

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 vertices, if degree of each vertex is 2, then Euler circuit exists in G.

is this statement true?

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

0

they are telling about two triangles as an example of S1

+1

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

thanks @srestha :)

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).
by (51 points)

1
2
+1 vote