Skip to main content

Timeline for Number of cliques in a graph

Current License: CC BY-SA 3.0

7 events
when toggle format what by license comment
Jul 26, 2017 at 17:17 vote accept m0_as
Jul 25, 2017 at 15:46 answer added John Kemeny timeline score: 5
Jul 25, 2017 at 1:29 comment added m0_as @D.W. Thanks, for a complete graph of $n$ vertices, I think the number of cliques is $n \choose 1$ + $n \choose 2$ + $\ldots$ + $n \choose n$ = $2^n$. Am I right?
Jul 24, 2017 at 22:53 comment added David Richerby This is an extremely straightforward observation (consider @D.W.'s suggestion) and a citation isn't required. Sure, you could probably find somebody who's published this fact but giving them a citation would look silly and they certainly won't have been the first person to make the observation.
Jul 24, 2017 at 22:48 comment added D.W. What have you tried? Have you tried counting the number of cliques in the complete graph on $n$ vertices, as a function of $n$?
Jul 24, 2017 at 22:32 comment added ryan I would recommend reading this: arxiv.org/abs/math/0602191
Jul 24, 2017 at 22:16 history asked m0_as CC BY-SA 3.0