# Find the number of graphs such that...

• Jul 7th 2009, 01:54 PM
Bruno J.
Find the number of graphs such that...
Find the number of undirected graphs on \$\displaystyle n\$ vertices such that, whenever there is a path \$\displaystyle a_1 \leftrightarrow a_2 \leftrightarrow ... \leftrightarrow a_k\$ joining the vertices \$\displaystyle a_1,...,a_k\$, then there is a complete graph on \$\displaystyle a_1,...,a_k\$.
• Jul 8th 2009, 12:51 AM
Swlabr
Quote:

Originally Posted by Bruno J.
Find the number of undirected graphs on \$\displaystyle n\$ vertices such that, whenever there is a path \$\displaystyle a_1 \leftrightarrow a_2 \leftrightarrow ... \leftrightarrow a_k\$ joining the vertices \$\displaystyle a_1,...,a_k\$, then there is a complete graph on \$\displaystyle a_1,...,a_k\$.

I can't think of any hints that wouldn't be completely and utterly cryptic, so I'll just sort of give you the logical leap bit, and is hopefully only a wee bit cryptic...presuming, of course, you didn't quite get the leap bit...

Basically, what you want to do find out how many ways there are of partitioning and n-element set.

I'm sure you can solve the problem from there.