$($a$)$ Using the backtracysing approach, determine if it is possible to color the following graph with $3$ colors such that no two adjacent vertices share the same color. The graph has vertices $A,B,C,D,E,F,$ and edges $(A,B),(A,C),(A,D),(B,C),(B,E),(C,F),(D,E),$ and $($E$,$ F$).$ Show each step of the backtracking process.

$($b$)$ Based on the backtracking strategy, briefly explain how the state space tree is constructed during the graph coloring process. How does backtracking prune the search space, and why is this important for efficiency?

$[5+3$ Marks$]$