Hey I am having trouble with this question:



I have that if a graph G is 5 regular then by the handshake theorem we get it has an even number of vertices and the number of edges is equal to 5k where k is an integer.

I am not sure how to go from here or if these are even relevant, if anyone could help that'd be great thank you.

Actually I have something so far but I need help proving just one thing inside my proof.

First I said suppose this decomposition exists. Then I proved that every vertex is an end vertex for each path.

Now let m be the number of vertices and n be the number of edges, by the handshake theorem, I get 5m = 2n which implies I have 5m/2 edges.

Since every vertex is an endpoint, I have at least m/2 paths. I need help seeing why this is true, because if I have this then I get:

If I have m/2 paths, and each path is of length 6, then this decomposition requires 3m edges, but my original graph only has 5m/2 edges, contradiction.

Can anyone help show me how to show the bold part is true?

You have an even number of vertices and you showed each vertex is an endpoint of some path. So you can say you have p end vertices. Each path uses 2 end vertices. So we conclude there mustbe at least p/2 paths