Can someone explain why we care so much about graphs in various branches of science? Like, why model the problems mentioned in the video as graphs that need to be colored?
And any time you can think of something as a graph, you can benefit from the wealth of available mathematical and computational tools that apply to all graphs.
After all, an (undirected) graph is nothing more than a ground set and a collection of its two-element subsets.
It's the same reason why groups crop up so often: groups are also really simple structures, so it's really easy to satisfy their axioms 'by accident'. Same for numbers in general.
Not that they would crop up, if you somehow randomly generated mathematical structure. The real world, and especially the part of the real world that people engage with, seems to have a lot of simple structures.
For example, in some cases it can be useful to consider triangles in a 3D model as cyclic graphs of vertices. The edges of the triangle correspond to the edges in the graph.
However I can't think of any case where it's useful to think of a triangle as a hashmap.
However what you gain in the simplicity of the ZKP, you lose in the reduction to 3-coloring. So nowadays people use ZKPs that work with more realistic computation representations, like arithmetic circuits
Graphs are just a very simple generalization of lists. And many problems can be easily modelled as graphs