Given a graph G, its chromatic number x(G) is the smallest number of colors we need to color it; that is, the smallest k such that it is k-colorable. Consider the following problem:

1- a classic peg solitaire game. In eachmove, a peg jumps over another, which is removed. Can you reduce this configuration of 8 pegs to a single peg in the center?

2-sliding-block puzzle. Can you move the big square block to the bottomcenter,where it can slide out of the box? The shortest solution has 81moves. Do you believe this problemis in NP? Why or why not?

Transcribed Image Text:

the Original ⒸVENTURE una co, ne. DALTON Ic TESTER Ma U.S.A. Deluxe Edition FELES OF THE GAME START WITH ANY ONE HOLE EMPTY AS YOU AMP THE PEOS REMOVE THEM FROM THE BOARD TRY TO LEAVE ONLY ONE PEG SCORING FOR BENDERS LEAVE THREE JUST 50-80 10 POINTS LEAVE TWO ABOVE VERAGE POINTS LEAVE ONE-VERY SMART 0 POINTS SCORING FOR ADVANCED PLAYER PED IN THE EXACT HOLE YOU INTIALLY LEPT EMPTY LLANT-10 POINTS LEAVE & PEGS ON THE BOARD WITH NO REMAINING JUMPS-GENIUS 20 PONTS utions at www.pegame.com Each fame a Solitary Adventure" the Original ⒸVENTURE una co, ne. DALTON Ic TESTER Ma U.S.A. Deluxe Edition FELES OF THE GAME START WITH ANY ONE HOLE EMPTY AS YOU AMP THE PEOS REMOVE THEM FROM THE BOARD TRY TO LEAVE ONLY ONE PEG SCORING FOR BENDERS LEAVE THREE JUST 50-80 10 POINTS LEAVE TWO ABOVE VERAGE POINTS LEAVE ONE-VERY SMART 0 POINTS SCORING FOR ADVANCED PLAYER PED IN THE EXACT HOLE YOU INTIALLY LEPT EMPTY LLANT-10 POINTS LEAVE & PEGS ON THE BOARD WITH NO REMAINING JUMPS-GENIUS 20 PONTS utions at www.pegame.com Each fame a Solitary Adventure"

Answer rating: 100% (QA)

Given a graph with N vertices and E edges The edges are given as U and V such that for each index i ... View the full answer