Prove or disprove: If $G = (V, E)$ is an undirected graph where every vertex has degree at
least 4 and $u \in V$, then there are at least $64$ distinct paths in $G$ that start at $u$.
- I tried to generate some counterexamples, but of course it is quite hard to find 64 paths for each one. I noticed that $64 = 4^3$. Maybe this is related to making a choice between two paths at least 3 times?
- I have no other ideas. Any help?
Best Answer
Let's count the number of paths we know exist. You can follow along on $K_5$, since that's the lower bound.
$4+12+24+24=64.$
This is, in fact, the total number of paths starting from a given vertex of $K_5$, so it is the best lower pound possible.