# 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?

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