Explore topic-wise InterviewSolutions in .

Correct option is (C) N – 1

The best explanation: A complete graph is the one in which each VERTEX is DIRECTLY connected with all other vertices with an edge. The CHROMATIC index for even number of vertices will be n-1.

The correct option is (a) n

Best EXPLANATION: A COMPLETE graph is the one in which each VERTEX is DIRECTLY connected with all other VERTICES with an edge. The chromatic index for an odd number of vertices will be n.

Right option is (c) 2

To EXPLAIN: The given graph will REQUIRE 2 unique colors so that no TWO incident edges have the same color. So its CHROMATIC index will be 2.

Correct answer is (b) 3

To explain: The GIVEN graph will require 3 unique colors so that no two INCIDENT edges have the same color. So its chromatic INDEX will be 3.

The correct choice is (b) 2

For explanation: The given graph will REQUIRE 2 UNIQUE colors so that no two incident edges have the same COLOR. So its CHROMATIC index will be 2.

The correct CHOICE is (a) True

The BEST I can explain: A BIPARTITE graph has an EDGE chromatic number equal to Δ. So bipartite GRAPHS belongs to class 1 graphs.

The correct ANSWER is (a) True

The best explanation: The CHROMATIC index of a GRAPH is always EQUAL to the chromatic number of its line graph. So we can calculate the chromatic index of a graph by calculating the chromatic number of its line graph.

Right ANSWER is (c) NP COMPLETE problem

The explanation is: Chromatic index of an arbitrary graph cannot be determined by using any convenient method. So CALCULATING the chromatic index of a graph is an NP complete problem.

The CORRECT choice is (d) The minimum number of colors REQUIRED for proper EDGE coloring of graph

Explanation: The minimum number of colors required for proper edge coloring of graph is called chromatic index whereas the minimum number of colors required for proper VERTEX coloring of graph is called chromatic number of a graph.

Correct CHOICE is (a) k edge COLORING graph

To explain: A proper edge coloring graph ENSURES that no two incident edges has the same color. If it uses k colors in the PROCESS then it is called k coloring of graph.

Correct answer is (c) No two INCIDENT edges should have the same color

Easy explanation - The CONDITION for proper EDGE coloring of GRAPH is that no two incident edges should have the same color. If it uses k colors in the PROCESS then it is called k edge coloring of graph.

Correct choice is (b) False

The explanation is: The chromatic number of a star graph and a TREE is ALWAYS 2 (for more than 1 vertex). So both have the same chromatic number.

Correct answer is (b) False

Easy explanation - The CHROMATIC NUMBER of a star GRAPH is always 2 (for more than 1 vertex) WHEREAS the chromatic number of complete graph with 3 vertices will be 3. So chromatic number of complete graph will be GREATER.

The CORRECT answer is (b) 3

Easiest explanation - The given graph will require 3 UNIQUE colors so that no two vertices connected by a COMMON edge will have the same color. So its chromatic NUMBER will be 3.

The CORRECT choice is (B) 2

Explanation: The given graph will only REQUIRE 2 UNIQUE colors so that no TWO vertices connected by a common edge will have the same color. So its chromatic number will be 2.

The correct CHOICE is (b) K COLORABLE

Easiest explanation - Any graph that has a chromatic number less than or EQUAL to k is called k colorable. WHEREAS a graph with chromatic number k is called k chromatic.

The correct option is (c) 2

Easy EXPLANATION - The minimum number of COLORS required for proper vertex COLORING of graph is CALLED chromatic number. So every tree having more than 1 vertex is 2 chromatic.

Right option is (d) n

For EXPLANATION: A LINE graph of a SIMPLE graph is OBTAINED by connecting two vertices with an edge. A line graph has a chromatic number of n.

The correct answer is (c) NP complete problem

The EXPLANATION is: CHROMATIC NUMBER of an arbitrary graph cannot be DETERMINED by using any convenient method. So calculating the chromatic number of a graph is an NP complete problem.

The correct OPTION is (B) 1

To EXPLAIN: An empty graph is a graph without any edges. So the chromatic number for such a graph will be 1.

Correct ANSWER is (C) The minimum number of COLORS REQUIRED for PROPER vertex coloring of graph

Explanation: The minimum number of colors required for proper vertex coloring of graph is called chromatic number whereas the minimum number of colors required for proper edge coloring of graph is called chromatic index of a graph.

Correct answer is (a) k coloring graph

To EXPLAIN: A PROPER graph ensures that two vertices which share a common edge should not have the same COLOR. If it uses k colors in the process then it is CALLED k coloring of graph.

Right answer is (a) two vertices having a common EDGE should not have same COLOR

Best explanation: The condition for proper COLORING of graph is that two vertices which SHARE a common edge should not have the same color. If it uses k colors in the process then it is CALLED k coloring of graph.

The correct option is (b) False

To explain: VERTEX coloring of a graph is an assignment of colors to the vertices of a graph such that no TWO ADJACENT vertices have the same color. Whereas chromatic number refers to the minimum number of UNIQUE colors REQUIRED for vertex coloring of the graph.

Correct OPTION is (b) 3

The EXPLANATION is: The given graph will REQUIRE 3 unique colors because two diagonal VERTEX are connected to each other directly. So its chromatic NUMBER will be 3.

Right CHOICE is (b) 2

Easy explanation - The GIVEN graph will only require 2 unique colors so that no TWO vertices connected by a COMMON EDGE will have the same color. All nodes will have the same color except the central node.

Correct option is (B) Chromatic index

The explanation is: The MINIMUM number of colors REQUIRED for PROPER edge coloring of graph is called chromatic index. It is also KNOWN as edge chromatic number.

The correct answer is (C) n

The BEST explanation: A complete GRAPH is the one in which each vertex is directly connected with all other vertices with an edge. So the number of UNIQUE colors required for proper coloring of the graph will be n.

Right ANSWER is (C) 2

Easiest explanation - A bipartite graph is a graph such that no two vertices of the same set are ADJACENT to each other. So the number of unique colors REQUIRED for PROPER coloring of the graph will be 2.

The correct choice is (b) 1

The best I can explain: An empty GRAPH is a graph WITHOUT any edges. So the NUMBER of unique colors required for proper COLORING of the graph will be 1.

The correct ANSWER is (c) chromatic number

To explain: The minimum number of colors REQUIRED for PROPER vertex coloring of graph is CALLED chromatic number whereas the minimum number of colors required for proper edge coloring of graph is called chromatic index of a graph.

The CORRECT answer is (c) N – 1

Easy explanation - In ORDER to have a fully CONNECTED tree it MUST have N-1 edges. So the correct answer will be N-1.

The correct answer is (a) A CONDITION where any two vertices having a common EDGE should not have same color

Easiest explanation - The condition for vertex coloring of a graph is that two vertices which share a common edge should not have the same color. If it USES K colors in the process then it is called k coloring of graph.

The correct option is (b) bar graph

Easy explanation - ACCORDING to the graph theory a graph is the COLLECTION of DOTS and LINES. A bar graph is not a TYPE of graph in computer science.