For a connected graph G with G 50 prove that there is a wal

For a connected graph G with |G| = 50, prove that there is a walk through all vertices with length no more than 96?

Solution

A walk in G is a finite (non-empty) sequence W = v₀e₁v₁e₂v₂ ...e_kv_k alternating vertices and edges such that, for 1 ? i ? k, v_i?1 and v_i are the endvertices of e_i. The vertex v₀ is called start of W and v_k terminus of W. They both are endvertices of W. The vertices v_i,1 ? i ? k?1 are the internal vertices. One says that W links v₀ to v_k and that W is a (v₀, v_k)-walk

in a walk repetation of vertex as well as edges are allowed therfore

If G is a graph, then the walk W is entirely determined by the sequence of its vertices. Very often, we will then denote W = (v₀, v₁,..., v_k). The length of W is k, which is its number of edges (with repetitions).

so with repetation

maximum no of edges are

2*(50-2)=96

that is walk through all vertex (when edges and vertex are repetated)