- #1

Superyoshiom

- 29

- 0

- Homework Statement
- Using induction, we need to prove that given a graph G where the number of edges is even, if we decompose it then there is a decomposition will create a set of paths of length 2

- Relevant Equations
- G = (V,E), where V are the vertices and E are the edges

For my base case I just used a graph with three vertices and 2 edges. Decomposing this would just give us the same graph, which has a path length of 2.

The inductive step is where I'm having some trouble: One idea I have is that we take a graph G then inductively remove an edge to create two parts of a graph. Assuming the graph has even edges to begin with, removing edges creates one subgraph with odd edges and one with even edges. Can I assume then, that the subgraph with even edges can be decomposed to make path lengths of 2?

Thank you in advance

The inductive step is where I'm having some trouble: One idea I have is that we take a graph G then inductively remove an edge to create two parts of a graph. Assuming the graph has even edges to begin with, removing edges creates one subgraph with odd edges and one with even edges. Can I assume then, that the subgraph with even edges can be decomposed to make path lengths of 2?

Thank you in advance