Graph Colouring #1

I hastily produced one puzzle, which should be pretty simple. There's only one small trick to it...

Graph Colouring Instructions

Here is a classic graph theory problem: Put numbers (or "colours") 1, 2, or 3 into each circle so that adjacent circles receive different numbers. I guess some puzzles may use more colours, and that will be indicated for each puzzle.

Here is a simple example:

Notice that the circle on the top is adjacent to circles already coloured 1 and 2. So that circle must be coloured with 3. Then the circle on the right must be coloured with 1. So the solution for this puzzle is
.

MinMax Path #1-3

I'll start off with three small instances of this puzzle. I'm not sure if it will still be interesting when the graph gets larger...

Puzzle #1


Puzzle #2


Puzzle #3

MinMax Path Instruction

Given a graph, assign to the edges of the graph weights 1, 2, ..., m where m is the total number of edges. Assign a unique weight to each edge. Then find a shortest path joining the two black vertices, where the "length" of the path is the sum of the weights of all the edges in the path. The goal is to find an assignment of the edges so that the length of the shortest path is as large as possible. Note that there may be several optimal ways of assigning the weights, but the optimal value is unique.

I guess this may be a bit confusing, so here is a simple example: There are 4 edges in this graph, so we need to put weights 1, 2, 3, 4 on the edges.

There are essentially three ways to put the weights...

The shortest path between the two black vertices in the first assignment is 3. This is 4 in the second assignment, and 5 in the third assignment. Since 5 is the largest of them all, this is the answer for this puzzle.