1A connected graph is called an Eulerian graph if it contains a closed walk that traverses:
Eulerian graphs
Easy
A.Every vertex exactly once
B.Every edge exactly once and returns to the start
C.Every vertex at least twice
D.Every edge at least twice
Correct Answer: Every edge exactly once and returns to the start
Explanation:
An Eulerian circuit traverses each edge of the graph exactly once and returns to the starting vertex. A graph having such a circuit is called an Eulerian graph.
Incorrect! Try again.
2According to Euler's theorem, a connected graph has an Euler circuit if and only if:
Euler theorem
Easy
A.The graph is complete
B.Every vertex has even degree
C.Exactly two vertices have odd degree
D.Every vertex has odd degree
Correct Answer: Every vertex has even degree
Explanation:
Euler's theorem states that a connected graph contains an Euler circuit if and only if the degree of every vertex is even.
Incorrect! Try again.
3A connected graph has an Euler path (but not a circuit) if and only if it has exactly:
Euler theorem
Easy
A.Zero vertices of odd degree
B.One vertex of odd degree
C.Two vertices of odd degree
D.Four vertices of odd degree
Correct Answer: Two vertices of odd degree
Explanation:
A connected graph has an Euler path that is not a circuit exactly when it contains precisely two vertices of odd degree.
Incorrect! Try again.
4A Hamiltonian cycle in a graph is a closed walk that passes through:
Hamiltonian graphs
Easy
A.Every vertex exactly once
B.Every edge exactly once
C.Every edge at least once
D.Every vertex at least twice
Correct Answer: Every vertex exactly once
Explanation:
A Hamiltonian cycle visits each vertex of the graph exactly once and returns to the starting vertex.
Incorrect! Try again.
5The key difference between an Eulerian circuit and a Hamiltonian cycle is that:
Hamiltonian graphs
Easy
A.Euler covers all vertices; Hamilton covers all edges
B.Both cover all vertices twice
C.Both cover all edges once
D.Euler covers all edges once; Hamilton covers all vertices once
Correct Answer: Euler covers all edges once; Hamilton covers all vertices once
Explanation:
An Eulerian circuit uses every edge exactly once, while a Hamiltonian cycle visits every vertex exactly once.
Incorrect! Try again.
6A graph is called a planar graph if it can be drawn in the plane so that:
planar graphs
Easy
A.All vertices lie on a circle
B.It has no cycles
C.No two edges cross each other
D.Every edge is a straight line
Correct Answer: No two edges cross each other
Explanation:
A planar graph can be drawn on a plane such that its edges intersect only at their endpoints, with no crossings.
Incorrect! Try again.
7In a planar representation of a graph, a region (or face) is:
regions
Easy
A.An area bounded by edges
B.A set of parallel edges
C.A vertex of high degree
D.A vertex with no edges
Correct Answer: An area bounded by edges
Explanation:
A region (face) of a planar graph is an area of the plane bounded by edges, including the single unbounded outer region.
Incorrect! Try again.
8Euler's formula for a connected planar graph relates vertices , edges , and regions as:
Euler formula
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
Euler's formula for a connected planar graph states , where counts all regions including the unbounded one.
Incorrect! Try again.
9A connected planar graph has vertices and edges. Using Euler's formula, the number of regions is:
Euler formula
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
By Euler's formula , we get , so .
Incorrect! Try again.
10Which of the following is a well-known example of a non-planar graph?
non planar graphs
Easy
A.
B.A tree
C.
D.
Correct Answer:
Explanation:
The complete graph cannot be drawn without edge crossings and is one of the two basic non-planar graphs.
Incorrect! Try again.
11The complete bipartite graph that is a classic example of a non-planar graph is:
non planar graphs
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
The graph (the 'utility graph') is non-planar and, together with , forms the basis of Kuratowski's theorem.
Incorrect! Try again.
12Kuratowski's theorem characterizes non-planarity using subgraphs related to:
Kuratowski's theorem (without proof)
Easy
A. and
B. and
C. and
D. and
Correct Answer: and
Explanation:
Kuratowski's theorem states that a graph is non-planar if and only if it contains a subgraph that is a subdivision of or .
Incorrect! Try again.
13In proper graph coloring, the main rule is that:
graph coloring
Easy
A.Only edges are colored
B.Adjacent vertices get the same color
C.All vertices get the same color
D.Adjacent vertices get different colors
Correct Answer: Adjacent vertices get different colors
Explanation:
A proper vertex coloring assigns colors so that no two adjacent vertices share the same color.
Incorrect! Try again.
14The chromatic number of a graph is defined as:
chromatic number of a graph
Easy
A.The minimum number of colors needed for a proper coloring
B.The total number of vertices in
C.The maximum degree of
D.The number of edges in
Correct Answer: The minimum number of colors needed for a proper coloring
Explanation:
The chromatic number is the smallest number of colors required to properly color the vertices of .
Incorrect! Try again.
15The chromatic number of any graph containing at least one edge is at least:
chromatic number of a graph
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
If a graph has an edge, its two endpoints are adjacent and need different colors, so at least colors are required.
Incorrect! Try again.
16The chromatic number of the complete graph is:
complete graph and its coloring
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
In every vertex is adjacent to every other vertex, so each of the vertices needs a distinct color, giving .
Incorrect! Try again.
17The chromatic number of the complete graph is:
complete graph and its coloring
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
For a complete graph , , so .
Incorrect! Try again.
18The chromatic number of any bipartite graph with at least one edge is:
regular and bipartite graphs and their coloring
Easy
A.
B.Equal to the number of vertices
C.
D.
Correct Answer:
Explanation:
A bipartite graph's vertices split into two sets with edges only between them, so it can always be properly colored with colors.
Incorrect! Try again.
19A graph in which every vertex has the same degree is called a:
regular and bipartite graphs and their coloring
Easy
A.Planar graph
B.Regular graph
C.Bipartite graph
D.Complete graph
Correct Answer: Regular graph
Explanation:
A regular graph is one in which all vertices have equal degree; if the common degree is , it is called -regular.
Incorrect! Try again.
20A graph is bipartite if and only if it contains no cycle of:
regular and bipartite graphs and their coloring
Easy
A.Length four
B.Length two
C.Even length
D.Odd length
Correct Answer: Odd length
Explanation:
A graph is bipartite exactly when it has no odd-length cycles, which is why bipartite graphs are always -colorable.
Incorrect! Try again.
21A connected graph has exactly two vertices of odd degree. Which of the following is true about ?
Eulerian graphs
Medium
A.It has an Euler path but no Euler circuit
B.It has an Euler circuit but no Euler path
C.It has both an Euler path and an Euler circuit
D.It has neither an Euler path nor an Euler circuit
Correct Answer: It has an Euler path but no Euler circuit
Explanation:
A connected graph has an Euler path (but not circuit) if and only if it has exactly two vertices of odd degree. The path must start and end at these two odd-degree vertices.
Incorrect! Try again.
22For which values of does the complete graph have an Euler circuit?
Euler theorem
Medium
A.Only
B.All even
C.All odd
D.All
Correct Answer: All odd
Explanation:
In , every vertex has degree . An Euler circuit requires all vertices to have even degree, so must be even, meaning is odd (and for the graph to be connected with a circuit).
Incorrect! Try again.
23A graph has vertices. According to Dirac's theorem, what minimum degree of every vertex guarantees that is Hamiltonian?
Hamiltonian graphs
Medium
A.Each vertex has degree at least
B.Each vertex has degree at least
C.Each vertex has degree at least
D.Each vertex has degree at least
Correct Answer: Each vertex has degree at least
Explanation:
Dirac's theorem states that if every vertex has degree at least , the graph is Hamiltonian. For , this gives degree .
Incorrect! Try again.
24A connected planar graph has vertices and edges. Using Euler's formula, how many regions does its planar embedding have?
Euler formula
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
Euler's formula states . Substituting, , so . This includes the unbounded outer region.
Incorrect! Try again.
25For a connected simple planar graph with vertices and edges, which inequality must hold?
planar graphs
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
This standard bound follows from Euler's formula combined with the fact that each face is bounded by at least edges. It is a necessary condition for planarity.
Incorrect! Try again.
26The complete graph has vertices and edges. Why does it violate the planarity condition?
non planar graphs
Medium
A.Because
B.Because
C.Because it has odd-degree vertices
D.Because it contains a triangle
Correct Answer: Because
Explanation:
The planarity bound requires . For , , but , so cannot be planar.
Incorrect! Try again.
27According to Kuratowski's theorem, a graph is non-planar if and only if it contains a subgraph that is a subdivision of which graphs?
Kuratowski's theorem (without proof)
Medium
A. or
B. or
C. or
D. or
Correct Answer: or
Explanation:
Kuratowski's theorem states a graph is planar if and only if it contains no subgraph that is a subdivision of (complete graph on 5 vertices) or (complete bipartite graph).
Incorrect! Try again.
28What is the chromatic number of the complete graph ?
chromatic number of a graph
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
In a complete graph, every vertex is adjacent to all others, so each vertex needs a distinct color. Therefore , giving .
Incorrect! Try again.
29What is the chromatic number of any bipartite graph that contains at least one edge?
regular and bipartite graphs and their coloring
Medium
A.It depends on the number of vertices
B.
C.
D.
Correct Answer:
Explanation:
A bipartite graph's vertices can be split into two independent sets. Each set gets one color, so when at least one edge exists (an edge forces at least two colors).
Incorrect! Try again.
30How many edges does the complete graph contain, and what is its chromatic number?
complete graph and its coloring
Medium
A. edges, chromatic number
B. edges, chromatic number
C. edges, chromatic number
D. edges, chromatic number
Correct Answer: edges, chromatic number
Explanation:
The number of edges in is , and its chromatic number is .
Incorrect! Try again.
31A cycle graph with an odd number of vertices requires how many colors for a proper vertex coloring?
graph coloring
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
An even cycle is 2-colorable, but an odd cycle cannot be 2-colored because it contains an odd number of vertices in a ring, forcing a color conflict. Thus for odd .
Incorrect! Try again.
32Which statement best describes the difference between an Eulerian and a Hamiltonian circuit?
Hamiltonian graphs
Medium
A.Both visit every edge exactly once
B.An Eulerian circuit visits every vertex exactly once, whereas a Hamiltonian circuit visits every edge exactly once
C.An Eulerian circuit visits every edge exactly once, whereas a Hamiltonian circuit visits every vertex exactly once
D.Both visit every vertex exactly once but differ in starting point
Correct Answer: An Eulerian circuit visits every edge exactly once, whereas a Hamiltonian circuit visits every vertex exactly once
Explanation:
An Eulerian circuit traverses each edge exactly once and returns to start; a Hamiltonian circuit visits each vertex exactly once and returns to start.
Incorrect! Try again.
33In a planar embedding of a connected graph, the sum of the degrees of all regions (faces) equals which quantity?
regions
Medium
A.The number of vertices
B.The number of edges
C.Twice the number of vertices
D.Twice the number of edges
Correct Answer: Twice the number of edges
Explanation:
Each edge borders exactly two regions (or is counted twice for the same region if it is a bridge), so the sum of all region degrees equals .
Incorrect! Try again.
34The complete bipartite graph has vertices and edges. Which reasoning correctly shows it is non-planar?
non planar graphs
Medium
A.It fails because it has a Hamiltonian cycle
B.It fails because all its vertices have odd degree
C.It fails because
D.It fails because using the bound that applies to bipartite (triangle-free) graphs
Correct Answer: It fails because using the bound that applies to bipartite (triangle-free) graphs
Explanation:
Since is triangle-free, each face has at least edges, giving the tighter bound . As , it is non-planar.
Incorrect! Try again.
35A connected graph has degree sequence . Does it have an Euler circuit?
Eulerian graphs
Medium
A.Cannot be determined from the degree sequence
B.Yes, because all vertices have even degree
C.No, because it has odd-degree vertices
D.No, because the number of edges is odd
Correct Answer: Yes, because all vertices have even degree
Explanation:
A connected graph has an Euler circuit if and only if every vertex has even degree. All degrees here () are even, so an Euler circuit exists.
Incorrect! Try again.
36What is the chromatic number of the Petersen graph, which is a well-known 3-regular graph with no triangles?
chromatic number of a graph
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The Petersen graph contains odd cycles (like 5-cycles), so it is not bipartite (). It can be properly colored with colors, so its chromatic number is .
Incorrect! Try again.
37A connected planar graph has regions and edges. How many vertices does it have?
Euler formula
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
By Euler's formula , so , giving .
Incorrect! Try again.
38A graph is -regular if every vertex has degree . What is the chromatic number of the complete bipartite graph , which is -regular?
regular and bipartite graphs and their coloring
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
Any complete bipartite graph is bipartite, and bipartite graphs with edges have chromatic number , regardless of regularity.
Incorrect! Try again.
39The Four Color Theorem states that any planar map can be colored with at most how many colors so that no two adjacent regions share a color?
maps
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The Four Color Theorem guarantees that the regions of any planar map (equivalently, vertices of any planar graph) can be properly colored using at most colors.
Incorrect! Try again.
40For a graph with maximum vertex degree , which of the following gives a general upper bound for the chromatic number established by Brooks' theorem for connected graphs that are neither complete nor an odd cycle?
graph coloring
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
Brooks' theorem states that for a connected graph that is neither a complete graph nor an odd cycle, . (Complete graphs and odd cycles are the exceptions requiring .)
Incorrect! Try again.
41A connected graph has exactly 4 vertices of odd degree. What is the minimum number of edge-disjoint open trails needed to cover all edges of exactly once?
Eulerian graphs
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
A connected graph with odd-degree vertices can be decomposed into exactly edge-disjoint open trails. With 4 odd vertices, , so 2 trails are needed.
Incorrect! Try again.
42For which values of does the complete graph contain an Euler circuit?
Euler theorem
Hard
A.Only
B.All
C.All odd
D.All even
Correct Answer: All odd
Explanation:
In every vertex has degree . An Euler circuit needs all degrees even, so must be even, meaning is odd. Thus is Eulerian for all odd .
Incorrect! Try again.
43By Dirac's theorem, a simple graph on vertices is Hamiltonian if every vertex has degree at least what value?
Hamiltonian graphs
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Dirac's theorem states that if every vertex of a simple graph with vertices has degree , then the graph has a Hamiltonian cycle.
Incorrect! Try again.
44A connected planar graph has vertices and edges. Using Euler's formula, how many regions (faces) does its planar embedding have?
Euler formula
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Euler's formula gives , so .
Incorrect! Try again.
45For a simple connected planar graph with vertices, which inequality must the number of edges satisfy?
planar graphs
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Each face is bounded by at least 3 edges and each edge borders 2 faces, giving . Combined with Euler's formula this yields .
Incorrect! Try again.
46Using the edge bound for bipartite planar graphs, what is the maximum number of edges a simple bipartite planar graph on vertices can have?
non planar graphs
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
In a bipartite graph every cycle has even length, so each face has at least 4 edges: . Combined with Euler's formula, .
Incorrect! Try again.
47What is the chromatic number of the complete bipartite graph ?
chromatic number of a graph
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Every complete bipartite graph is bipartite and contains at least one edge, so its chromatic number is exactly .
Incorrect! Try again.
48What is the chromatic number of the complete graph ?
complete graph and its coloring
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
In every pair of vertices is adjacent, so no two vertices can share a color. Hence exactly colors are required and .
Incorrect! Try again.
49According to Kuratowski's theorem, a graph is non-planar if and only if it contains a subgraph that is a subdivision of which graphs?
Kuratowski's theorem (without proof)
Hard
A. or
B. or
C. or
D. or
Correct Answer: or
Explanation:
Kuratowski's theorem states a graph is planar iff it contains no subgraph that is a subdivision of (complete graph on 5 vertices) or (complete bipartite graph).
Incorrect! Try again.
50Consider the Petersen graph, which is -regular with vertices. What is its chromatic number?
regular and bipartite graphs and their coloring
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The Petersen graph is not bipartite (it contains odd cycles), so . A valid 3-coloring exists, so its chromatic number is exactly .
Incorrect! Try again.
51A connected planar simple graph has vertices, each of degree . How many regions does its planar embedding have?
regions
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Sum of degrees , so . By Euler's formula, .
Incorrect! Try again.
52Which statement about the relationship between Eulerian and Hamiltonian graphs is correct?
Hamiltonian graphs
Hard
A.A graph is Hamiltonian iff it is Eulerian
B.Every Eulerian graph is Hamiltonian
C.A graph can be Eulerian but not Hamiltonian and vice versa
D.Every Hamiltonian graph is Eulerian
Correct Answer: A graph can be Eulerian but not Hamiltonian and vice versa
Explanation:
The two properties are independent. For example, is Eulerian but not Hamiltonian, while is Hamiltonian but not Eulerian (odd degrees).
Incorrect! Try again.
53By Brooks' theorem, for a connected graph that is neither a complete graph nor an odd cycle, the chromatic number satisfies which bound?
graph coloring
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Brooks' theorem states that for a connected graph that is neither complete nor an odd cycle, , where is the maximum degree.
Incorrect! Try again.
54The graph has vertices and edges. Why does the bipartite planarity bound prove it is non-planar?
non planar graphs
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
For bipartite planar graphs . Here , but has edges. Since , it violates the bound and is non-planar.
Incorrect! Try again.
55A connected multigraph has an Euler trail (open, not closed) if and only if it has exactly how many vertices of odd degree?
Euler theorem
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
An Euler trail that is not a circuit exists iff the connected graph has exactly two odd-degree vertices, which serve as the trail's endpoints.
Incorrect! Try again.
56What is the chromatic number of a cycle graph when is odd?
chromatic number of a graph
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
An even cycle is bipartite (), but an odd cycle cannot be 2-colored because of its odd length, requiring exactly colors.
Incorrect! Try again.
57Which of the following statements about the dual of a planar graph is correct?
planar graphs
Hard
A.Regions of become vertices of the dual
B.The dual of a tree is another tree
C. always has fewer edges than
D.Vertices of become regions of
Correct Answer: Regions of become vertices of the dual
Explanation:
In the dual of a planar embedding, each region (face) of corresponds to a vertex of , and adjacent faces are joined by dual edges crossing shared edges.
Incorrect! Try again.
58The Four Color Theorem guarantees that any planar map can be colored with at most how many colors so that no two adjacent regions share a color?
maps
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The Four Color Theorem states that the regions of any planar map (equivalently the vertices of any planar graph) can be colored with at most colors so adjacent regions differ.
Incorrect! Try again.
59A -regular bipartite graph is guaranteed to have which chromatic index (edge chromatic number) by König's theorem?
regular and bipartite graphs and their coloring
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
König's edge-coloring theorem states that every bipartite graph has chromatic index equal to its maximum degree. For a -regular bipartite graph, this equals .
Incorrect! Try again.
60Consider the complete bipartite graph . Under which condition is it Eulerian?
Eulerian graphs
Hard
A.Both and are odd
B.Both and are even
C.At least one of is even
D. is even
Correct Answer: Both and are even
Explanation:
In , vertices in one part have degree and in the other have degree . All degrees are even iff both and are even, which (with connectivity) makes it Eulerian.
Incorrect! Try again.
Did this save you a night before the exam?
LPU Notes is free, and it stays free. Ads cover part of the server bill.
The rest comes out of a student's own pocket: the domain, the storage,
and keeping the site up through the weeks everyone needs it at once.
The payment button didn't load. An ad blocker or a filtered network is the usual reason.
to try again.
Nothing here is ever locked, and nothing unlocks. Chip in only if it was worth it.
What it pays for →