Find the number of paths of length 5 in the complete bipartite graph $K_{4,9}$.

Question

<Graph Theory>
Find the number of paths of length 5 in the complete bipartite graph $K_{4,9}$.

amistre64 · Answer

complete means each vertex is connected to all other vertexes.  bi partite ... 2 parts?  might have to help me out on the definitions to start with

anonymous · Answer

Yes.|dw:1386335216748:dw|

amistre64 · Answer

hmm, yeah i was thinking something similar but with all the verts hit .. but then it wouldnt be bipartite would it

amistre64 · Answer

and a path cannot hit the same vert more than once can it

anonymous · Answer

I think it can. Also, that graph I drew is a bipartite graph.

amistre64 · Answer

|dw:1386335363104:dw|

the degree of verts in a path are 1 at the ends and 2 along the way;  start, in-out, end

anonymous · Answer

Oh NO!
It can only hit one vertex more than once, that is the starting vertex :O

anonymous · Answer

|dw:1386335840974:dw|

amistre64 · Answer

correct, a path must have distinct or unique edges and verts.

amistre64 · Answer

i dont see or recall a formula for determining this in my text :/  would have to take it to paper

amistre64 · Answer

i can see a permutation, but not sure if i can see a combination

anonymous · Answer

Do you mean P(4,3) * P(9, 3) ?

anonymous · Answer

|dw:1386336233244:dw|