### venkycodes's blog

By venkycodes, history, 2 months ago, ,

Hi. I was wondering if there is any upperbound to the size of euler walk with respect to number of vertices. If yes then what will be that maximizing condition?

• 0

 » 2 months ago, # |   0 Auto comment: topic has been updated by venkycodes (previous revision, new revision, compare).
 » 2 months ago, # | ← Rev. 3 →   +3  the number of times any node will be added to the euler walk is equal to number of its children every tree + 1 for non leaf nodes and 2 times for leaves (for upper bound we can assume that number of times a node occurs in a euler walk is equal to Nc + 2 where NcI is the number of children of a node I) for each node we can safely assume that every child gives it a single contribution and it has 2 contribution from itself in its frequency in euler path now every node will be child of exactly one node except root (neglect it for now ) and this will contribute one frequency of its parent so total N(number of nodes in tree ) will be added to the euler vector size, and for each node 2 will be added as per above analysis hence at most 2*N will be added to the euler vector so total euler vector size should not increase 3*Nhope it is correct tell me if I am wrong somewhere
 » 2 months ago, # |   +6 If by "euler walk" you're referring to the Eulerian path/cycle in a general graph, then the length of that is exactly the number of edges in the graph. If you're talking about the Euler tour of a tree, then the number of vertices in the tour is exactly $2|V|-1$.
•  » » 2 months ago, # ^ |   +6 can you tell me how it would be exactly 2v-1 ?
•  » » » 2 months ago, # ^ |   +6 There are $|V|-1$ edges, and we traverse each of them twice. Once going down, and once going back up. So that's a total of $2|V|-2$ edge traversals. We start out with the root vertex and each time we traverse an edge we add a new vertex, so total is $2|V|-1$.