If you look at their Contexts, you'll see that all of them are in the System` context and not the GraphUtilities` context.
Context /@ {GraphDistanceMatrix, CharacteristicPolynomial, AdjacencyMatrix}
Out[1]= {"System`", "System`", "System`"}
Some packages are preloaded when the kernel starts — System` is one of them, whereas GraphUtilities` is not. You can see all packages that are pre-loaded with $Packages
$Packages
Out[2]= {"ResourceLocator`", "DocumentationSearch`", "GetFEKernelInit`",
"JLink`", "PacletManager`", "WebServices`", "System`", "Global`"}