Short Quiz (FinalQ in DS)

What is the goal of graph coloring?

• To assign colors to vertices so that adjacent vertices share the same color

• To assign colors to vertices so that no adjacent vertices share the same color

• To assign colors randomly to vertices

• To maximize the number of colors used

What is the chromatic number of a bipartite graph?

• 1

• 2

• 3

• Depends on the number of vertices

What is the chromatic number of a graph with 6 vertices forming a cycle?

• 2

• 3

• 4

• 6

What is the chromatic number of a graph with no edges?

• 1

• Equal to the number of vertices

• 2

• Depends on the graph type

Which graph type can always be colored with 2 colors?

• Complete graph

• Cycle graph

• Bipartite graph

• Disconnected graph

Simplify the equation: 124 = 31 * x. What is the value of x?

• 4

• 8

• 16

• 24

What does the Right Cancellation Law state?

• ^{𝑏𝑜𝑎=𝑐𝑜𝑎⇒𝑏=𝑐 for all 𝑎,𝑏,𝑐 ∈ 𝐺}

• _{𝑏𝑜𝑎=𝑐𝑜𝑎 ⇒ 𝑎 =𝑏 for all 𝑎,𝑏,𝑐 ∈ 𝐺}

• ^{boa=coa ⇒ a = c}

  ^{for all a,b,c ∈ G}

• ^{boa=coa ⇒ a = 0 for all a,b, c ∈ G}

What is the role of symmetry in discrete structures?

• To analyze and solve problems using symmetry principles

• To create asymmetric relations

• To remove elements from sets

• To define continuous functions

How does symmetry simplify problems in graph theory?

• By removing vertices and edges

• By simplifying connectivity, optimization, and coloring problems

• By adding more vertices to the graph

• By making graphs asymmetric

What is the definition of a symmetric relation?

• A relation where every ordered pair has its reverse included

• A relation where no ordered pairs are included

• A relation where only one ordered pair exists

• A relation where all elements are unrelated