How Many Graphs on n Vertices? | Graph Theory

We count the number of simple graphs there are on n vertices. We are counting labeled graphs, so we're answering the question of how many graphs there are with vertex set {1, 2, 3, ..., n}. This requires we know how many edges are possible on n vertices, and then the result is straightforward. #GraphTheory

◉Textbooks I Like◉

★DONATE★

Thanks to Petar, dric, Rolf Waefler, Robert Rennie, Barbara Sharrock, Joshua Gray, Karl Kristiansen, Katy, Mohamad Nossier, and Shadow Master for their generous support on Patreon!

Follow Wrath of Math on...

[rhl_]

While revising graph theory, i was just stuck on how many labelled graphs n vertices have. Knowing the answers doesn't work in mathematics anymore. It's more important to know why the answer is that. That sudden irritated feeling when you couldn't recall as toh why the answer is that only. So I sit patiently and searches stack overflow, as usual the answer is too hard to understand for someone as dense like me. Opens YouTube. Only clicks on your video coz of neat presentation. Turns out the best decision of my entire day.
Thank you so much man, very intuitive solution and the example for n = 3 really cleared many misconceptions. Thanks again.
Good day :)

[simonamohammad]

Hi there, I find your video to be very useful and well done 😄. They saved my life multiple times. By any chance at some points can you cover Turan graphs and multipartite graphs?

[aditi]

your videos have actually helped me understand some data structures in compsci better!

[conformitycontrol]

Hey at the end of the video, you said you would link a video on counting vertices in non-isomorphic graphs. Do you have that video up?

[Roblobster]

Great Youtube Series, So for just an n amount of vertices you can have 2^(n C 2) graphs. I am trying to find out how many simple graphs you can make without isolated vertices. If I represent an isolated vertices by k would the function just change to 2^(n-k C 2)? Since you would be subtracting graphs that have k amount of isolated vertices? I may be over-simplyfing it. Not sure. Any ideas?

[adamgurdikyan]

Hi there i there were a few things on Graph theory I didn’t rly understand, I was just wondering the best way to reach out

[dgt]

What if we talk just about connected graphs?

[luciano]

riders of the storm dun dunnn dun dunn dun dunnn dun

[PunmasterSTP]

Idk man, this video was kinda...edgy.