Graph Theory – How to Write Proofs on Paths in Graph Theory

graph theoryproof-writing

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.

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

Related Question