FourColour.fs

type Country = string
type Chart     = Set<Country*Country>
type Colour     = Set<Country>
type Colouring  = Set<Colour>

let areNeighbours (chart:Chart) (firstCountry:Country) (secondCountry:Country) :bool = 
    chart.Contains((firstCountry,secondCountry)) || chart.Contains((secondCountry,firstCountry))

let canBeExtBy (chart:Chart) (colour:Colour) (country:Country) :bool =
    colour
    |> Set.forall(fun candidate -> candidate |> areNeighbours chart country |> not)

let extColouring (chart:Chart) (colouring:Colouring) (country:Country) =
    let newColouring, wasAdded =
        colouring
        |> Set.fold(fun (current,flag) colour -> 
            if flag || canBeExtBy chart colour country |> not then
                (current |> Set.add colour, flag)
            else
                (current |> Set.add (colour |> Set.add country), true)) (Set.empty,false)
    if wasAdded then
        newColouring
    else
        newColouring
        |> Set.add (country |> Set.singleton)

let countries  (chart:Chart) :Colour =
    (chart |> Set.map(fun (country,_)->country),chart |> Set.map(fun (_,country)->country))
    ||> Set.union

let colCntrs (chart:Chart) (countries:Set<Country>) =
    countries
    |> Set.fold (fun current country->extColouring chart current country) Set.empty

let colMap chart = colCntrs chart (countries chart)

let exMap = 
    [("Andorra", "Benin"); ("Andorra", "Canada"); ("Andorra", "Denmark");
    ("Benin", "Canada"); ("Benin", "Denmark"); ("Canada", "Denmark");
    ("Estonia", "Canada"); ("Estonia", "Denmark"); ("Estonia", "Finland")] 
    |> Set.ofList

colMap exMap

Opinionated "corrections" and comments below....

type Country    = string
type Chart      = Set<Country*Country>
type Colour     = Set<Country>
type Colouring  = Set<Colour>

let areNeighbours (chart:Chart) (firstCountry:Country) (secondCountry:Country) :bool =
    // Seems a tad more "idiomatic"/functional
    [ firstCountry, secondCountry; secondCountry, firstCountry ]
    |> List.exists (fun pair -> Set.contains pair chart)

let canBeExtendedBy (chart:Chart) (colour:Colour) (country:Country) :bool =
    colour
    // Since you already reordered the arguments correctly, we can now replace the lambda with
    // partial application and function composition
    |> Set.forall (areNeighbours chart country >> not)

let extendColouring (chart:Chart) (colouring:Colouring) (country:Country) =
    let newColouring, wasAddedToExistingColour =
        // Having the 'initial state' tuple at the end of the last line of that slightly complex
        // lambda with a good number of parentheses is irritating, because you first have to figure
        // out which parentheses group what, so it's probably clearer to have it up here.
        // Also, `fold` generally is rather difficult to understand, so it helps to be really
        // explicit with naming (at least for the next reader).
        ((Set.empty, false), colouring) 
        ||> Set.fold(fun (accumulatorColouring, alreadyAdded) currentColour ->
            // Clearer about what the `not` applies to
            if alreadyAdded || not (canBeExtendedBy chart currentColour country) then
                (accumulatorColouring |> Set.add currentColour, alreadyAdded)
            else
                (accumulatorColouring |> Set.add (currentColour |> Set.add country), true)) 

    if wasAddedToExistingColour then
        newColouring
    else
        newColouring
        |> Set.add (country |> Set.singleton)

let countriesInChart (chart:Chart) : Colour =
    // This avoids going through the set twice.
    chart
    |> Seq.collect (fun (first, second) -> [ first; second ])
    |> Set.ofSeq

let countriesInChartAlternative (chart : Chart) : Colour =
    // The original version of this function can be simplified by replacing the lambdas.
    // `fst` and `snd` are built-in functions that return the first and second values of a pair-tuple
    (chart |> Set.map fst, chart |> Set.map snd)
    ||> Set.union

let colourCodeCountries (chart:Chart) (countries:Set<Country>) =
    // Again, the order of the arguments to `extendColouring` allows us to use partial application
    // in place of that lambda.
    countries |> Set.fold (extendColouring chart) Set.empty

let colourCodeMap chart = colourCodeCountries chart (countriesInChart chart)

let exMap = 
    [("Andorra", "Benin"); ("Andorra", "Canada"); ("Andorra", "Denmark");
    ("Benin", "Canada"); ("Benin", "Denmark"); ("Canada", "Denmark");
    ("Estonia", "Canada"); ("Estonia", "Denmark"); ("Estonia", "Finland")] 
    |> Set.ofList

colourCodeMap exMap