Graph Theory Proofs on Paths

Question

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?

Answer 1

Let's count the number of paths we know exist. You can follow along on $K_5$, since that's the lower bound.

• There are 4 paths of length 1.
• For each of those, there are at least three paths of length 2, since each of those vertices has four neighbors but we can't go back to $u$. So the graph has 12 paths of length 2.
• For each of those, there are at least two paths of length 3, again you can't return to the previous two vertices in the path. So there are at least 24 paths of length 3.
• Third verse same as the first: each path of length 3 can be extended to at least one path of length 4, so there are 24 paths of length 4.

$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.

Answer 2

I don't think that this is true. For a counterexample, take $G = K_5$ and label the vertices $V = \{u, a, b, c, d\}$. Then there are $4!$ paths of length $5$ which start at $u$ (e.g.: $u \to a \to b \to c \to d$ and $u \to c \to b \to a \to d$). Counting up all such paths over all possible lengths, we have: $$ 4! + 3! + 2! + 1! + 0! = 34 < 64 $$