In this paper, we are interested in computing the number of edge colourings and total colourings of a connected graph. We prove that the maximum number of k‐edge‐colourings of a connected k‐regular graph on n vertices is k⋅((k−1)!)
n/2. Our proof is constructive and leads to a branching algorithm enumerating all the k‐edge‐colourings of a connected k‐regular graph in time O
∗(((k−1)!)
n/2) and polynomial space. In particular, we obtain a algorithm to enumerate all the 3‐edge‐colourings of a connected cubic graph in time O
∗(2
n/2)=O
∗(1.4143
n
) and polynomial space. This improves the running time of O
∗(1.5423
n
) of the algorithm due to Golovach et al. (2010). We also show that the number of 4‐total‐colourings of a connected cubic graph is at most 3·23n/2. Again, our proof yields a branching algorithm to enumerate all the 4‐total‐colourings of a connected cubic graph.
