0:00:00.000,0:00:02.000
Here's our last random graph of this unit.

0:00:02.000,0:00:05.000
We're going to again generate a graph on n nodes recursively.

0:00:05.000,0:00:07.000
Same structure as before.

0:00:07.000,0:00:09.000
If there's 1 node, we just return that node.

0:00:09.000,0:00:12.000
Otherwise, we do it recursively.

0:00:12.000,0:00:15.000
So we generate a graph on n/2 nodes--call that G1.

0:00:15.000,0:00:18.000
We generate a graph on n/2 nodes and call it G2--different graph.

0:00:18.000,0:00:21.000
Now we randomly scramble the nodes in those two,

0:00:21.000,0:00:24.000
keeping the edges in their appropriate way.

0:00:24.000,0:00:26.000
Just consider them in a particular order.

0:00:26.000,0:00:30.000
Then we connect the first node in this ordering in G1 to the first node in this ordering in G2,

0:00:30.000,0:00:34.000
the second one in this ordering in G1 to the second one in G2,

0:00:34.000,0:00:37.000
third one to the third one, forth one to the forth one, and so on.

0:00:37.000,0:00:41.000
Now we get a set of edges that now breach across these two graphs,

0:00:41.000,0:00:43.000
and we call this G and return it.

0:00:43.000,0:00:45.000
So based on this random generation process we can ask,

0:00:45.000,0:00:47.000
what kind of graph structure did we make?

0:00:47.000,0:00:51.000
Is it a ring, a tree, a hypercube, or maybe none of these?