Question

1. color the vertices of the following graph ( g_2 ).

the chromatic number is (\boxed{quad}).

Explanation:

Step1: Identify adjacent vertices

List vertex adjacencies:

• $a$: $v, c$
• $v$: $a, u, c$
• $c$: $a, v, x$
• $u$: $v, m, w, x$
• $m$: $u, x$
• $x$: $c, m, u, w$
• $w$: $u, x$

Step2: Check for odd cycles

The subgraph $a-v-c-a$ is a triangle (3-cycle, odd). This means the graph is not bipartite, so at least 3 colors are needed.

Step3: Test 3-coloring

Assign colors as follows:

• Color 1: $a, m, w$
• Color 2: $v, x$
• Color 3: $c, u$

Verify no adjacent vertices share the same color:

• $a$ (1) adjacent to $v$ (2), $c$ (3) ✔️
• $v$ (2) adjacent to $a$ (1), $u$ (3), $c$ (3) ✔️
• $c$ (3) adjacent to $a$ (1), $v$ (2), $x$ (2) ✔️
• $u$ (3) adjacent to $v$ (2), $m$ (1), $w$ (1), $x$ (2) ✔️
• $m$ (1) adjacent to $u$ (3), $x$ (2) ✔️
• $x$ (2) adjacent to $c$ (3), $m$ (1), $u$ (3), $w$ (1) ✔️
• $w$ (1) adjacent to $u$ (3), $x$ (2) ✔️

Step4: Confirm chromatic number

A valid 3-coloring exists, and an odd cycle makes 2 colors impossible.

Answer:

The chromatic number is 3.
Vertex coloring assignment (example):

• Color 1: $a, m, w$
• Color 2: $v, x$
• Color 3: $c, u$