1. Suppose that x1,. ,...,xk+1 is a circuit of length k in a graph G (x...

Transcribed Image Text:

1. Suppose that x1,. ,...,xk+1 is a circuit of length k in a graph G (x = xk+1) of length 3 or greater (k 3). Suppose as well that the circuit does not repeat edges (ie xx+1 xjxj+1 for i j). Show that G contains a cycle. (Hint: you can't necessarily use the circuit itself as the cyclic subgraph, but you can modify it). 2. Suppose that every vertex of a graph, G, has degree > 2. Show that G contains a cycle. 1. Suppose that x1,. ,...,xk+1 is a circuit of length k in a graph G (x = xk+1) of length 3 or greater (k 3). Suppose as well that the circuit does not repeat edges (ie xx+1 xjxj+1 for i j). Show that G contains a cycle. (Hint: you can't necessarily use the circuit itself as the cyclic subgraph, but you can modify it). 2. Suppose that every vertex of a graph, G, has degree > 2. Show that G contains a cycle.