A graph is a set of things and the connections between them, with no rule about where a connection may go. That freedom is why graphs can model friendships, road maps and recommendations, where connections run in every direction and a tree's one-parent rule doesn't hold.
Nodes and edges
A graph has two parts. Nodes (also called vertices) are the things, and edges are the connections between pairs of them. In the video, each cat is a node and each friendship is an edge.
This is the graph data structure, not the bar chart or line graph from maths lessons. A chart plots values against axes; a graph data structure records which things are connected to which.
Take the four cats from the video. Fluffy knows Mittens, Mittens knows Whiskers, Whiskers knows Shadow, and Shadow knows Fluffy. Here are those four friendships as a graph:
Start at Fluffy and follow the edges: Mittens, Whiskers, Shadow, then back to Fluffy. A path that ends where it started is called a cycle (the video calls it a loop). Graphs allow cycles, and real data is full of them.
Why a tree can't hold it
A tree is a stricter kind of graph. It has one root at the top, every other node has exactly one parent, and there is exactly one path between any two nodes. That rules out cycles. The rules are what make trees easy to work with: folders on a disk, the elements of a web page and a company's reporting lines all fit them.
Try to fit the cats into one. Put Mittens at the top, with Fluffy and Whiskers as her children, and Shadow under Whiskers. So far every cat has one parent. Now add the last friendship: Shadow knows Fluffy. Fluffy would need Shadow as a second parent, and there are now two paths from Mittens to Fluffy. The tree's rules break.
Once a node can have more than one parent, or connections can lead back to where they started, you need a graph.
Directed, undirected and weighted
Wondering how this was made? How we make these