[go: up one dir, main page]
Scribd
Upload
193 views3 pages

Question Bank For PG Course Mathematics: Graph Theory: Pgmt-Viiib

This document contains 30 questions about graph theory topics like simple graphs, digraphs, complete graphs, forests, trees, planar graphs, Euler's formula, Hamiltonian paths and trees. The questions test concepts like the number of edges in different graph types, properties of planar graphs, conditions for connectivity and planarity.

Uploaded by

Abhishek Vajpayee
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
193 views3 pages

Question Bank For PG Course Mathematics: Graph Theory: Pgmt-Viiib

This document contains 30 questions about graph theory topics like simple graphs, digraphs, complete graphs, forests, trees, planar graphs, Euler's formula, Hamiltonian paths and trees. The questions test concepts like the number of edges in different graph types, properties of planar graphs, conditions for connectivity and planarity.

Uploaded by

Abhishek Vajpayee
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Question Bank For PG Course

Mathematics
Paper-8B
GRAPH THEORY : PGMT-VIIIB

Question 1

What is a simple graph?

Question 2

Question 3

How does a Digraph representing a reflexive binary relation be recognized?

Question 4

Question 5

Find the number of edges in a complete graph G with n vertices.

Question 6

Question 7

Question 8

Find the number of edges in a forest with n vertices and k components.

Question 9
Question 10

When is Kruskal’s algorithm used ?

Question 11

What is the Height of a rooted tree ?

Question 12

What is the maximum number of vertices in an m-tree at level p ?

Question 13

Find the relation between the height h and the number of vertices n of a complete binary tree T.

Question 14

If G is a connected planar graph with n vertices, e edges and f faces, then write down Euler’s formula.

Question 15

Let G be a connected 4-regular planar graph with 8 vertices. How many faces does G have ?

Question 16

What are two or more edges of a Graph known as when they are incident with the same pair of distinct vertices?

Question 17

How many vertices of equal degree must a simple graph with n ( ≥ 2) vertices have?

Question 18

Can there be a simple graph with 8 vertices and 30 edges?

Question 19

Two graphs G and H are such that there exist a one-to-one correspondence f : VG→ VH and also a one-to-one correspondenceФ : EG→EH so that for every
eє EG with end points u, v in VG , the function f maps u and v to the endpoints of Ф( e ) in VH. What is the similarity between the graphs G and H?
Question 20

Let G be a simple graph with n vertices and m components. Find the maximum number of edges G can have.

Question 21

Write down the necessary and sufficient condition for a graph G with vertex set V to be disconnected.

Question 22

A simple connected graph G remains connected after the removal of an edge. What type of edge is it?

Question 23

Find the number of edges in a complete graph G with n vertices.

Question 24

State the necessary and sufficient condition for a simple graph to be bipartite.

Question 25

What is the length of a Hamiltonian path in a simple n-vertex graph?

Question 26

State a necessary and sufficient condition that a connected graph G contain an Euler trail.

Question 27

Suppose that 10 villages are to be provided electricity laying a wired network from one common source. The costs of direct wiring between each pair of
villages are known. Which tool of graph theory can be used to find the least expensive network that connects all the villages?

Question 28

What is the relation between the height h and the number of leaves k in a binary tree T?

Question 29

State a necessary and sufficient condition for a graph to be a planar graph.

Question 30

Is it possible to draw a tree with 10 vertices of degree 2, 3 vertices of degree 3, 4 vertices of degree 1?

You might also like