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

Access detailed explanations (illustrated with images and videos) to 2122 questions. Access all new questions- tracking exam pattern and syllabus. View the complete topic-wise distribution of questions. Unlimited Access, Unlimited Time, on Unlimited Devices!

View Sample Explanation or View Features.

Rs. 550.00 -OR-

How to register? Already Subscribed?

Question 1

Graph Theory

Appeared in Year: 2013 (UGC-NET)

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

Question 2

Graph Theory

Appeared in Year: 2015 (UGC-NET)

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)

Question 3

Graph Theory

Appeared in Year: 2016 (UGC-NET)

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

Developed by: