On Tue, Jan 08, 2019 at 05:53:25PM -0500, Tom Lane wrote:
> John Naylor <john.naylor@2ndquadrant.com> writes:
> > -As for the graph algorithm, I'd have to play with it to understand
> > how it works.
>
> I improved the comment about how come the hash table entry assignment
> works. One thing I'm not clear about myself is
>
> # A cycle-free graph is either empty or has some vertex of degree 1.
>
> That sounds like a standard graph theory result, but I'm not familiar
> with a proof for it.
Let's assume all vertexes have a degree > 1, the graph is acyclic and
non-empty. Pick any vertex. Let's construct a path now starting from
this vertex. It is connected to at least one other vertex. Let's follow
that path. Again, there must be connected to one more vertex and it can't
go back to the starting point (since that would be a cycle). The next
vertex must still have another connections and it can't go back to any
already visited vertexes. Continue until you run out of vertex...
Joerg