Graph Theory [GATE (Graduate Aptitude Test in Engineering) Computer Science]: Questions 1 - 3 of 62

Access detailed explanations (illustrated with images and videos) to 2290 questions. Access all new questions- tracking exam pattern and syllabus. View the complete topic-wise distribution of questions. 3 Year Validity- Access Unlimited Times on Unlimited Devices.

View Sample Explanation or View Features.

Rs. 600.00 -OR-

How to register? Already Subscribed?

Question 1

Appeared in Year: 2013

Question MCQ▾

Which of the following statement (s) is/are false?

  1. A connected multigraph has an Euler Circuit if and only if each of its vertices has even degree.
  2. A connected multigraph has an Euler Path but not an Euler Circuit if and only if it has exactly two vertices of odd degree.
  3. A complete graph (KN) has a Hamilton Circuit whenever n ⩾ 3
  4. A cycle over six vertices (C6) is not a bipartite graph but a complete graph over 3 vertices is bipartite. (Dec)

Choices

Choice (4)Response

a.

(1) only

b.

(2) and (3)

c.

(3) only

d.

(4) only

Edit

Question 2

Appeared in Year: 2015

Question MCQ▾

A tree with n vertices is called graceful, if its vertices can be labelled with integers 1,2, … , n such that the absolute value of the difference of the labels of adjacent vertices are all different. Which of the following trees are graceful?

Labelling of Graceful Graphs

Choices

Choice (4)Response

a.

(a) and (c)

b.

(b) and (c)

c.

(a) , (b) and (c)

d.

(a) and (b)

Edit

Question 3

Appeared in Year: 2016

Question MCQ▾

The number of different spanning trees in complete graph, and bipartite graph have … and … respectively.

Choices

Choice (4)Response

a.

14,14

b.

16,4

c.

16,14

d.

14,4

Edit