# 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

Appeared in Year: *2013 (UGC-NET)*

### Question

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

- A connected multigraph has an Euler Circuit if and only if each of its vertices has even degree.
- A connected multigraph has an Euler Path but not an Euler Circuit if and only if it has exactly two vertices of odd degree.
- A complete graph (K
_{N}) has a Hamilton Circuit whenever n ⩾ 3 - A cycle over six vertices (C
_{6}) 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

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?

### Choices

Choice (4) | Response | |
---|---|---|

a. | (a) and (c) | |

b. | (b) and (c) | |

c. | (a) , (b) and (c) | |

d. | (a) and (b) |

## Question 3

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 |