GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
193 views

asked in Graph Theory by Boss (9.1k points) 4 64 210 | 193 views
Do we always need to take some graphs and check options by hit and trial in graph theory or they can be done using some axioms.?

1 Answer

+1 vote
We can solve this type of problem by assuming graph which holds true for their constraint given,

For statement  1 and 2 ,  graph contain six vertices and have degree = 2 ( for each node )

simple graph  , graph which have no multiple edges and self loop is known as simple graph but it can   be connected or not.

each node have two degree means , each node is connected with two different nodes , because simple graph doesn't have multiple edges or self loop.

Then graph have to be cyclic like [ A - B - C - D - E - F - A ] ,   all  have degree equals to two.

Hence statement one is true.

Second, euler circuit : start from any node , traverse each edge exactly once and come back to the starting node is know as euler circuit, which is true for this graph, hence statement 2 is correct.

Statement 3 :   you can surely draw a graph, which have no self loop and no multiple edges, and have degree equals to three , and it is disconnected.

Hence s1 and s2 is correct , s3 is not.
answered by Loyal (2.9k points) 3 17
reverese is true.
S1: Two complete graph of 3 vertices. Each vertex having degree 2. Graph is disconnected.

 

S2: Same graph as above. Since it's disconnected, no Euler circuit will be there.

 

S3: A graph on set of 8 vertices, consisting of two components. Each component being a complete graph of 4 vertices.

 

Now tell me, what's wrong with this.
Yep, all options are true or false on different - different simple  graph...

Option A :  Onlys S1 is true,  (false )  because  statement 2 and 3 can also be false.

Option B : S1 and S2 are true , yep ,  possibble ,  they together be true  or false

Option C : Only S3 is true , false   , s1 and s2 can be true

Option D : S2 and S3 are true ,  its not necessary they together be true, both are independent of each other

Hence option B is correct.
The question is not talking about a particular graph, so the answer has to be universally correct. You are trying to choose one of the options just for the sake of it.

 

Correct answer is All the given statements are false.
I have already specified that all statements are true or false on different - different graph, but we have to mark any option out of given.   

Anyways thanks , for noticing !!
thanks akash. all are false
here multiple edge meaning parallel edges between two nodes


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
Top Users Oct 2017
  1. Arjun

    23462 Points

  2. Bikram

    17108 Points

  3. Habibkhan

    8560 Points

  4. srestha

    6314 Points

  5. Debashish Deka

    5458 Points

  6. jothee

    5038 Points

  7. Sachin Mittal 1

    4882 Points

  8. joshi_nitish

    4416 Points

  9. sushmita

    3996 Points

  10. Rishi yadav

    3868 Points


Recent Badges

Regular Anuranjan Chauhan
Famous Question pC
Notable Question Sanjay Sharma
Notable Question Warrior
Notable Question sid1221
Nice Answer 2018
Good Question Arjun
Nice Question mitalitak
Great Question Arjun
Popular Question Tesla!
27,349 questions
35,204 answers
84,249 comments
33,328 users