Discrete Math Quiz: Graph Coloring
20 questions · exam conditions
0:00
Graph ColoringQuestion 1 of 20

In a proper vertex coloring of a graph G, let c(v) denote the color assigned to vertex v. Define the 'color sum' of an edge (u,v) as c(u) + c(v). If G is a triangle (3-cycle) and we want to minimize the maximum color sum over all edges while using the minimum number of colors, what is this minimum maximum color sum?

4, achieved by using colors 1, 2, 3 with maximum sum being min(1+2, 2+3, 1+3) = 4
5, achieved by using colors 1, 2, 3 with maximum sum being max(1+2, 2+3, 1+3) = 5
3, achieved by using colors 1, 2, 3 with all edge sums being equal to 3
6, achieved by using colors 1, 2, 3 with some edge sums reaching this maximum
← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Graph Coloring

Practice Graph Coloring in Discrete Math with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Graph Coloring, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

In a proper vertex coloring of a graph G, let c(v) denote the color assigned to vertex v. Define the 'color sum' of an edge (u,v) as c(u) + c(v). If G is a triangle (3-cycle) and we want to minimize the maximum color sum over all edges while using the minimum number of colors, what is this minimum maximum color sum?

  1. 4, achieved by using colors 1, 2, 3 with maximum sum being min(1+2, 2+3, 1+3) = 4
  2. 5, achieved by using colors 1, 2, 3 with maximum sum being max(1+2, 2+3, 1+3) = 5 (correct answer)
  3. 3, achieved by using colors 1, 2, 3 with all edge sums being equal to 3
  4. 6, achieved by using colors 1, 2, 3 with some edge sums reaching this maximum
Explanation: A triangle requires 3 colors for proper coloring. Using colors 1, 2, 3, the three edges have color sums: 1+2=3, 2+3=5, and 1+3=4. The maximum of these sums is 5. This is optimal because: (1) we must use at least 3 distinct colors, (2) to minimize the maximum sum, we should use the smallest possible colors {1,2,3}, and (3) among all ways to assign these colors, the maximum edge sum is always 5 (the sum of the two largest colors).

Question 2

A university schedules final exams such that no student takes two exams simultaneously. The conflict graph has vertices representing exams and edges connecting exams with common students. If this graph is planar and contains no triangles, what is the minimum number of time slots needed if there are 20 exams and 25 conflicts?

  1. At most 3 time slots, since triangle-free planar graphs have chromatic number at most 3 (correct answer)
  2. At most 4 time slots, since all planar graphs satisfy the four-color theorem
  3. Exactly 4 time slots, since the graph density suggests high chromatic number
  4. Cannot be determined without knowing the specific graph structure and vertex degrees
Explanation: Triangle-free planar graphs have chromatic number at most 3. This is a stronger result than the general four-color theorem for planar graphs. The specific numbers of vertices and edges don't change this upper bound. Choice B gives a weaker bound. Choice C incorrectly assumes the chromatic number equals 4. Choice D is wrong because the triangle-free planar condition is sufficient.

Question 3

Consider the edge-coloring problem for a graph GG where each edge must be assigned a color such that no two edges sharing a vertex have the same color. If GG is a cubic graph (every vertex has degree 3) with 10 vertices, what is the minimum number of edge colors needed?

  1. 3 colors, since the maximum degree is 3 and Vizing's theorem guarantees this suffices
  2. 4 colors, since Vizing's theorem shows cubic graphs require either 3 or 4 colors
  3. 5 colors, since the graph has 15 edges and overlapping constraints increase requirements
  4. Either 3 or 4 colors depending on the specific cubic graph structure (correct answer)
Explanation: By Vizing's theorem, the edge chromatic number of any graph is either Δ\Delta or Δ+1\Delta + 1, where Δ\Delta is the maximum degree. For cubic graphs, Δ=3\Delta = 3, so either 3 or 4 colors are needed depending on whether the graph is Class 1 or Class 2. The specific structure determines which case applies. Choice A assumes all cubic graphs are Class 1. Choice B incorrectly suggests 4 is always needed. Choice C uses irrelevant reasoning about edge count.

Question 4

In a list coloring problem, each vertex vv has an available color list L(v)L(v). A graph is said to be kk-choosable if it can be properly colored whenever every vertex has a list of at least kk colors. How does the choice number relate to the chromatic number?

  1. The choice number always equals the chromatic number for any graph
  2. The choice number is always at least the chromatic number, but can be strictly larger (correct answer)
  3. The choice number can be either larger or smaller than the chromatic number depending on the graph
  4. The choice number equals the chromatic number for bipartite graphs but differs for other graphs
Explanation: The choice number (list chromatic number) is always at least the chromatic number, since having kk colors available to each vertex includes the case where all vertices use the same kk colors. However, the choice number can be strictly larger - for example, complete bipartite graphs Kr,rK_{r,r} have chromatic number 2 but choice number r+1r+1. Choice A is incorrect. Choice C wrongly suggests the choice number can be smaller. Choice D makes an incorrect specific claim about bipartite graphs.

Question 5

A graph GG has the property that it can be properly colored with kk colors, and in every such kk-coloring, there exists at least one color class containing exactly one vertex. What does this imply about the structure of GG?

  1. GG contains a vertex of degree k−1k-1 that is adjacent to vertices of all other colors
  2. GG has a universal vertex connected to all other vertices in the graph
  3. GG has chromatic number exactly kk and contains a vertex whose removal reduces chromatic number to k−1k-1 (correct answer)
  4. GG must be a complete graph or contain a complete subgraph of size kk
Explanation: If every kk-coloring has a singleton color class, then GG cannot be colored with k−1k-1 colors (otherwise we could redistribute the singleton vertex's color). This means χ(G)=k\chi(G) = k. Moreover, there exists a vertex vv such that χ(G−v)=k−1\chi(G-v) = k-1 (the singleton vertex), since removing it allows the remaining graph to use one fewer color. Choice A is too specific about degree. Choice B is unnecessarily strong. Choice D confuses chromatic number with clique number.

Question 6

A telecommunications company needs to assign frequencies to cell towers in a region to avoid interference. Two towers require different frequencies if they are within 50 miles of each other. If the tower network can be modeled as a graph where vertices represent towers and edges connect towers within 50 miles, and this graph has chromatic number 4, what is the minimum number of frequencies needed?

  1. 3 frequencies, since chromatic number represents the maximum needed
  2. 4 frequencies, since this equals the chromatic number exactly (correct answer)
  3. 5 frequencies, since we need one more than the chromatic number for safety
  4. It depends on the specific graph structure and cannot be determined
Explanation: The chromatic number of a graph is defined as the minimum number of colors needed to color all vertices such that no two adjacent vertices share the same color. Since the chromatic number is 4, exactly 4 frequencies are needed. Choice A confuses chromatic number with maximum degree plus one. Choice C incorrectly adds a safety margin. Choice D is wrong because chromatic number gives the exact minimum.

Question 7

A company assigns shifts to workers such that certain pairs cannot work simultaneously due to conflicts. The conflict graph is triangle-free and has independence number α=8\alpha = 8. If the graph has 20 vertices, what is the minimum number of shifts needed?

  1. At most 8 shifts, since the independence number provides the upper bound
  2. At least 3 shifts, since ⌈20/8⌉=3\lceil 20/8 \rceil = 3 and this is achievable for triangle-free graphs
  3. Exactly 3 shifts, since triangle-free graphs with independence number 8 have chromatic number 3
  4. At least 3 shifts, but could require more depending on the specific graph structure (correct answer)
Explanation: The chromatic number χ(G)≥⌈n/α⌉=⌈20/8⌉=3\chi(G) \geq \lceil n/\alpha \rceil = \lceil 20/8 \rceil = 3, so at least 3 shifts are needed. However, being triangle-free doesn't guarantee that exactly 3 colors suffice - the graph could still require more colors depending on its structure. Choice A confuses upper and lower bounds. Choice B incorrectly claims 3 is always achievable. Choice C makes an unjustified assertion about triangle-free graphs.

Question 8

A map coloring problem requires that adjacent regions use different colors, and regions that share only a corner point may use the same color. If a map contains exactly one region that borders all other regions, and there are 6 regions total, what can be concluded about the minimum number of colors needed?

  1. Exactly 4 colors are needed since the central region forces all others to use different colors
  2. At most 3 colors are needed since the 5 outer regions can share colors appropriately
  3. At least 2 colors are needed, but the exact number depends on adjacencies among outer regions (correct answer)
  4. Exactly 2 colors are needed since regions can alternate colors around the central region
Explanation: Let the central region use color 1. The 5 outer regions cannot use color 1, but they may use the same colors as each other if they're not adjacent. In the best case, if no outer regions are adjacent to each other, we need only 2 colors total (1 for center, 1 for all outer). In the worst case, if some outer regions are adjacent, we need additional colors. We definitely need at least 2 colors (one for the center, one for the outer regions), but the exact number depends on the adjacency pattern among the outer regions.

Question 9

In a list coloring problem, each vertex v has an associated list L(v) of available colors, and a proper list coloring assigns each vertex a color from its list such that adjacent vertices get different colors. Consider a path graph P₄ with vertices v₁, v₂, v₃, v₄ (in order) where L(v₁) = {1,2}, L(v₂) = {1,3}, L(v₃) = {2,3}, and L(v₄) = {2,3}. How many proper list colorings exist?

  1. 4 colorings since there are multiple valid assignments satisfying all constraints
  2. 0 colorings since the given lists make proper coloring impossible
  3. 1 coloring since the constraints uniquely determine the color assignment
  4. 2 colorings since the middle vertices severely constrain the possible assignments (correct answer)
Explanation: When you encounter list coloring problems, you need to systematically work through the constraints, checking which color assignments satisfy the adjacency requirements. In a path graph, each vertex can only be adjacent to its immediate neighbors. Let's analyze the path P4P_4 with vertices v1,v2,v3,v4v_1, v_2, v_3, v_4 connected in sequence. Start by examining the most constrained vertex. Here, v2v_2 is crucial because it's adjacent to both v1v_1 and v3v_3, and its list L(v2)={1,3}L(v_2) = \{1,3\} gives us two cases to consider. Case 1: If v2v_2 gets color 1, then v1v_1 (adjacent to v2v_2) cannot use color 1, so v1v_1 must be color 2. Similarly, v3v_3 cannot use color 1, so v3v_3 gets color 2 or 3. Since v1=2v_1 = 2, we need v3=3v_3 = 3 to avoid conflict. Finally, v4v_4 is adjacent to v3=3v_3 = 3, so v4=2v_4 = 2. This gives us coloring: (2,1,3,2). Case 2: If v2v_2 gets color 3, then v3v_3 must be color 2. This forces v1=1v_1 = 1 or 2, but since v2=3v_2 = 3, either works. If v1=2v_1 = 2, then v4=3v_4 = 3. This gives us coloring: (2,3,2,3). Answer choice A incorrectly counts 4 colorings by missing the constraint analysis. Choice B wrongly assumes impossibility without checking systematically. Choice C misses the second valid coloring by not considering both cases for v2v_2. Study tip: Always identify the most constrained vertices first (those with fewer color options or more neighbors), then build your solution systematically from there.

Question 10

A telecommunications network is modeled as a graph where vertices represent towers and edges represent direct communication links. The network requires frequency assignment such that towers within 2 hops of each other must use different frequencies. If the underlying graph is a path with 8 vertices, what is the minimum number of frequencies needed?

  1. 3 frequencies since the square of a path graph has chromatic number 3 (correct answer)
  2. 4 frequencies since we need to color the 2nd power of the path graph optimally
  3. 5 frequencies since the maximum degree in the squared graph determines the chromatic number
  4. 8 frequencies since each vertex must be distinguishable from all vertices within distance 2
Explanation: We need to find the chromatic number of P₈², the square of path P₈. In P₈², each vertex is adjacent to all vertices within distance 2 in the original path. The vertices can be partitioned into 3 independent sets: {1,4,7}, {2,5,8}, and {3,6}. Since we can 3-color the graph and the maximum clique size is 3 (e.g., vertices 1,2,3 form a triangle in P₈²), the chromatic number is exactly 3.

Question 11

Consider the edge coloring problem for a complete bipartite graph K₃,₄. An edge coloring assigns colors to edges such that no two edges sharing a vertex have the same color. What is the minimum number of colors needed for a proper edge coloring of K₃,₄?

  1. 3 colors since this equals the size of the smaller vertex set in the bipartition
  2. 4 colors since this equals the maximum degree of any vertex in the graph (correct answer)
  3. 7 colors since this equals the total number of vertices in the graph
  4. 12 colors since this equals the total number of edges in the graph
Explanation: The chromatic index (edge chromatic number) of any graph is at least the maximum degree Δ. In K₃,₄, vertices in the 3-vertex set each have degree 4, and vertices in the 4-vertex set each have degree 3, so Δ = 4. By Vizing's theorem, the chromatic index is either Δ or Δ+1. For complete bipartite graphs Kₘ,ₙ, the chromatic index equals max(m,n). Since max(3,4) = 4, exactly 4 colors are needed.

Question 12

A company needs to schedule meetings for 7 departments, where certain pairs cannot meet simultaneously due to shared personnel. The conflict relationships form a graph where departments A and B are connected if they cannot meet at the same time. If this conflict graph contains a cycle of length 5 and has chromatic number 4, what is the minimum number of time slots needed if we add one additional constraint that departments C and D (currently non-adjacent) must now avoid meeting simultaneously?

  1. The minimum remains 4 time slots since the chromatic number cannot increase by more than 1
  2. The minimum becomes 5 time slots since adding any edge to an odd cycle increases chromatic number by 1
  3. The minimum could be 4 or 5 time slots depending on how the new edge affects existing colorings (correct answer)
  4. The minimum becomes 6 time slots since we now have 7 departments with additional constraints
Explanation: Adding an edge to a graph can increase the chromatic number by at most 1. Since the original chromatic number is 4, the new chromatic number is at most 5. However, whether it actually increases depends on the specific structure. If C and D were assigned the same color in some optimal 4-coloring of the original graph, then adding the edge C-D would force us to use a 5th color. But if C and D had different colors in all optimal 4-colorings, then 4 colors still suffice. Without knowing the exact positions of C and D in the conflict graph, both outcomes are possible.

Question 13

A graph G has the property that it can be properly 2-colored, but after adding any single edge between non-adjacent vertices, the resulting graph requires 3 colors. What is the maximum number of edges that G can have if it has 8 vertices?

  1. 16 edges since G must be a complete bipartite graph to satisfy these conditions (correct answer)
  2. 12 edges since G can have at most this many edges while remaining bipartite
  3. 28 edges since this is the maximum possible for any graph on 8 vertices
  4. 15 edges since adding any edge to a near-complete bipartite graph creates odd cycles
Explanation: Since G is 2-colorable, it's bipartite. The condition that adding any edge creates a graph requiring 3 colors means adding any edge creates an odd cycle. This happens when G is a complete bipartite graph - adding any edge between non-adjacent vertices would create a triangle. For 8 vertices, the complete bipartite graph with maximum edges is K₄,₄, which has 4×4 = 16 edges. This is indeed maximal because if G were missing any edge from a complete bipartite graph, we could add that edge without creating an odd cycle.

Question 14

Consider a graph GG where every vertex has degree at most dd. A student claims that GG can always be properly colored using exactly dd colors. Which statement best describes this claim?

  1. True, because Brooks' theorem guarantees χ(G)≤d\chi(G) \leq d for all graphs
  2. False, because the chromatic number can exceed the maximum degree in certain graphs
  3. True for connected graphs only, false for disconnected graphs with isolated vertices
  4. False, because while χ(G)≤d+1\chi(G) \leq d + 1 always holds, χ(G)≤d\chi(G) \leq d requires additional conditions (correct answer)
Explanation: By the greedy coloring algorithm, any graph can be colored with at most Δ+1\Delta + 1 colors where Δ\Delta is the maximum degree. However, coloring with exactly Δ\Delta colors requires that the graph is neither a complete graph nor an odd cycle (Brooks' theorem). Choice A misses the exceptions. Choice B is too broad. Choice C incorrectly focuses on connectivity.

Question 15

A graph GG has chromatic polynomial P(x)=x(x−1)(x−2)(x−3)17P(x) = x(x-1)(x-2)(x-3)^{17}. What can be concluded about the structure of GG?

  1. GG has exactly 20 vertices and chromatic number 4 with maximum clique size 4 (correct answer)
  2. GG has exactly 20 vertices and chromatic number 4, but maximum clique size could be less than 4
  3. GG has chromatic number 4, but the number of vertices cannot be determined from this polynomial
  4. GG is a complete 4-partite graph with one part of size 17 and three parts of size 1
Explanation: The degree of the chromatic polynomial equals the number of vertices (20). The chromatic number equals the smallest positive integer kk such that P(k)>0P(k) > 0, which is 4. Since the polynomial has factors (x−1),(x−2),(x−3)(x-1), (x-2), (x-3), we have P(1)=P(2)=P(3)=0P(1) = P(2) = P(3) = 0, meaning the graph contains cliques of sizes 2, 3, and 4, so the maximum clique size is 4. Choice B underestimates clique size. Choices C and D miss key structural information.

Question 16

In a proper vertex coloring of a bipartite graph with parts AA and BB where ∣A∣=15|A| = 15 and ∣B∣=23|B| = 23, what is the relationship between the minimum colors needed and the graph structure?

  1. Exactly 2 colors are needed since bipartite graphs always have chromatic number 2 (correct answer)
  2. At least 15 colors are needed to accommodate the smaller partition completely
  3. The number of colors depends on the maximum degree of vertices in the graph
  4. Exactly 2 colors are needed unless the graph contains isolated vertices requiring fewer
Explanation: All bipartite graphs (with at least one edge) have chromatic number exactly 2, regardless of partition sizes or degree distribution. One color is assigned to all vertices in part A, another to all vertices in part B. No adjacent vertices share colors since edges only exist between parts. Choice B confuses vertex coloring with other problems. Choice C is irrelevant for bipartite graphs. Choice D incorrectly suggests isolated vertices change the chromatic number.

Question 17

A graph GG has chromatic number 4 and contains a vertex vv such that G−vG - v (the graph with vv removed) has chromatic number 3. What can be concluded about vertex vv?

  1. Vertex vv must be in every maximum clique of GG of size 4
  2. Vertex vv must have degree at least 4 to force the chromatic number increase
  3. Vertex vv must be adjacent to vertices of three different colors in any 3-coloring of G−vG - v (correct answer)
  4. Vertex vv must be connected to all other vertices in GG (i.e., vv is universal)
Explanation: When you encounter chromatic number problems involving vertex removal, focus on what happens to the coloring when you add the vertex back. The chromatic number is the minimum number of colors needed to properly color all vertices so no adjacent vertices share the same color. Since G−vG - v has chromatic number 3, you can color all vertices except vv using exactly three colors. Now, when you add vv back to get graph GG, the chromatic number jumps to 4, meaning vv cannot be colored with any of the three colors already used. This is only possible if vv is adjacent to at least one vertex of each of the three colors in the 3-coloring of G−vG - v. Therefore, vv requires a fourth color, making answer C correct. Let's examine why the other options fail. Option A is wrong because vv doesn't need to be in every maximum clique of size 4 – the chromatic number increase only requires vv to be adjacent to three differently colored vertices, not necessarily forming a 4-clique. Option B incorrectly assumes degree determines chromatic impact. While vv needs degree at least 3 (to reach three different colors), having degree 4 or higher doesn't guarantee a chromatic number increase if those neighbors aren't all different colors. Option D is far too strong – vv only needs to connect to representatives of each color class, not every single vertex. Remember: chromatic number problems often hinge on adjacency patterns and color conflicts, not just degree counts or clique membership.

Question 18

A graph GG has the property that in any proper coloring with the minimum number of colors, every color class has exactly the same size. What type of graph structure does this constraint suggest?

  1. GG must be a complete multipartite graph with equal part sizes (correct answer)
  2. GG must be vertex-transitive with high symmetry but not necessarily complete multipartite
  3. GG must be regular with all vertices having the same degree
  4. GG can be any graph where the vertex count is divisible by the chromatic number
Explanation: If every optimal coloring has equal-sized color classes, then GG must be a complete multipartite graph with equal part sizes. In such graphs, vertices in different parts must have different colors (due to complete connections between parts), and vertices within parts can share colors. This forces the balanced coloring. Choice B is too general. Choice C confuses regularity with chromatic properties. Choice D ignores structural requirements.

Question 19

In a proper coloring of a wheel graph WnW_n (consisting of a cycle CnC_n plus a central vertex connected to all vertices of the cycle), how does the chromatic number depend on nn?

  1. Always 4 colors regardless of nn, since the central vertex and cycle structure determine this
  2. 3 colors when nn is even, 4 colors when nn is odd (correct answer)
  3. 4 colors when nn is even, 3 colors when nn is odd
  4. Always 3 colors, since cycles can be 2-colored and the center needs a third color
Explanation: The cycle CnC_n requires 2 colors when nn is even and 3 colors when nn is odd. The central vertex is adjacent to all cycle vertices, so it needs a color different from all cycle colors. When nn is even: cycle uses 2 colors, center needs a 3rd (total: 3). When nn is odd: cycle uses 3 colors, center needs a 4th (total: 4). Choice A ignores the cycle's parity dependence. Choice C reverses the relationship. Choice D incorrectly assumes cycles always use 2 colors.

Question 20

A graph GG has a proper 3-coloring where each color class contains exactly kk vertices. If GG also has a perfect matching, what constraint must kk satisfy?

  1. kk must be even, since perfect matchings require even vertex count in each component
  2. kk can be any positive integer, since color classes and matching edges are independent
  3. kk must be divisible by 3, since the total vertices 3k3k must enable perfect matching
  4. kk must be even, since GG has 3k3k vertices and perfect matchings require even total vertex count (correct answer)
Explanation: A perfect matching pairs every vertex with exactly one other vertex, so the total number of vertices must be even. Since GG has 3k3k vertices total (kk in each of 3 color classes), we need 3k3k to be even, which requires kk to be even. Choice A incorrectly focuses on individual components rather than total count. Choice B ignores the constraint. Choice C uses wrong divisibility logic.