The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+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?
in Graph Theory by Junior (853 points) | 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.

2 Answers

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

Related questions

+6 votes
2 answers
1
asked Oct 10, 2016 in Graph Theory by Rahul Jain25 Boss (11k points) | 390 views
+2 votes
1 answer
2
asked Dec 28, 2016 in Graph Theory by thor Loyal (6.7k points) | 466 views
0 votes
1 answer
4
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
50,339 questions
55,765 answers
192,354 comments
90,815 users