The Gateway to Computer Science Excellence
+2 votes
346 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?
in Graph Theory by Junior | 346 views
0
both true
0

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

we dont know how many vertices

0
could you please explain how S2 is true?
0
yes sorry 2nd one not 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
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
0
i dont think so we can have 2 triangles
0
oh i missed this point thanks then you are right

it will not always true
0
that's why both must be wrong
0

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

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

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

2 Answers

+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

 

by Loyal
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
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

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

@aditi19

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

answer updated

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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,218 questions
59,890 answers
201,084 comments
118,128 users