Scribd
Upload
11 views3 pages

Graph Theory Questions and Answers

The document contains a series of questions and answers related to graph theory, covering topics such as Hamiltonian cycles, vertex coloring, triangle-free graphs, Berge graphs, and properties of finite graphs. Each question presents multiple-choice answers with the correct answer indicated. The questions test knowledge on various graph concepts and properties.

Uploaded by

Archit Raj
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
11 views3 pages

Graph Theory Questions and Answers

The document contains a series of questions and answers related to graph theory, covering topics such as Hamiltonian cycles, vertex coloring, triangle-free graphs, Berge graphs, and properties of finite graphs. Each question presents multiple-choice answers with the correct answer indicated. The questions test knowledge on various graph concepts and properties.

Uploaded by

Archit Raj
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

Graph Theory

Ques1. In a 7-node directed cyclic graph, the number of Hamiltonian cycle is to be


______
a) 728
b) 450
c) 360
d) 260

Answer: c

Ques2. . If each and every vertex in G has degree at most 23 then G can have a vertex
colouring of __________
a) 24
b) 23
c) 176
d) 54

Answer: a

Ques3. Triangle free graphs have the property of clique number is __________
a) less than 2
b) equal to 2
c) greater than 3
d) more than 10

Answer: d

Ques4. Berge graph is similar to ______ due to strong perfect graph theorem.
a) line graph
b) perfect graph
c) bar graph
d) triangle free graph

Answer: b

Ques5. Let D be a simple graph on 10 vertices such that there is a vertex of degree 1,
a vertex of degree 2, a vertex of degree 3, a vertex of degree 4, a vertex of degree 5, a
vertex of degree 6, a vertex of degree 7, a vertex of degree 8 and a vertex of degree 9.
What can be the degree of the last vertex?
Graph Theory
a) 4
b) 0
c) 2
d) 5

Answer: c

Ques6. A ______ is a graph which has the same number of edges as its complement
must have number of vertices congruent to 4m or 4m modulo 4(for integral values of
number of edges).
a) Subgraph
b) Hamiltonian graph
c) Euler graph
d) Self complementary graph

Answer: d

Ques7. In a ______ the vertex set and the edge set are finite sets.
a) finite graph
b) bipartite graph
c) infinite graph
d) connected graph

Answer: b

Ques8. If G is the forest with 54 vertices and 17 connected components, G has


_______ total number of edges.
a) 38
b) 37
c) 17/54
d) 17/53

Answer: b

Ques9. The number of edges in a regular graph of degree 46 and 8 vertices is


____________
a) 347
b) 230
Graph Theory
c) 184
d) 186

Answer: c

Ques10. An undirected graph G has bit strings of length 100 in its vertices and there is
an edge between vertex u and vertex v if and only if u and v differ in exactly one bit position.
Determine the ratio of the chromatic number of G to the diameter of G?
a) 1/2101
b) 1/50
c) 1/100
d) 1/20

Answer: b

Common questions

Powered by AI

In a bipartite graph, the vertex set and the edge set must be finite sets, meaning such graphs are inherently finite .

The degree of the last vertex must be 2 to maintain a simple 10-vertex graph where all other vertices have unique degrees from 1 to 9 .

A graph where each vertex has a degree at most 23 can have a vertex coloring using no more than 24 colors .

Triangle-free graphs have the property that their clique number is greater than 3, suggesting fewer restrictive conditions regarding connected subgraphs .

A 7-node directed cyclic graph has 360 Hamiltonian cycles .

A regular graph with a degree of 46 and 8 vertices has 184 edges .

A Berge graph is classified similarly to a perfect graph due to the strong perfect graph theorem .

Graphs are self-complementary when the number of vertices is congruent to 0 or 1 modulo 4, meaning they must have vertices congruent to 4m (for integral values of m).

The ratio of the chromatic number to the diameter of such a graph is 1/50 .

A forest with 54 vertices and 17 connected components has 37 edges, calculated by subtracting the number of components from the number of vertices (54 - 17).

You might also like