Since you've shown no work of your own, I'm forced to assume you have none to show (because you

*definitely* read the

**Read Before Posting thread** that's stickied at the top of each sub-forum, right?

) and you're stuck at the very beginning. For a problem like this, it's probably best to start with the definitions of the terms involved.

What is the definition of the cycle graph C

_{6}? In particular, how many vertices does it have? How many edges does it have? All of the vertices have the same degree. What degree is that? What is the definition of the path graph P

_{4}? How many vertices does it have? How many edges does it have? All but two of its vertices have the same degree. What degree is that? Which vertices have a different degree, and what degree are they? Finally, what is the definition of a [vertex] induced subgraph? What does it mean for a graph to have a vertex induced subgraph of C

_{6}? What does it mean for a graph to have a vertex induced subgraph of P

_{4}? Can both of these happen at the same time? If so, under what conditions do they both occur?

The goal of this problem is to determine whether or not an arbitrary graph can have a vertex induced subgraph of C

_{6} but not have a vertex induced subgraph of P

_{4}. If you think this can happen, finding one such example will suffice. However, if you think it cannot happen, then you need to provide a proof that every graph which has C

_{6} as a vertex induced subgraph also has P

_{4} as a vertex induced subgraph.