Does graph G exist s.t. G has induced subgraph cycle C6 but no inducd sbgrph path P4?
- Thread starter axel1
- Start date
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 C6? 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 P4? 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 C6? What does it mean for a graph to have a vertex induced subgraph of P4? 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 C6 but not have a vertex induced subgraph of P4. 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 C6 as a vertex induced subgraph also has P4 as a vertex induced subgraph.
) 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 C6? 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 P4? 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 C6? What does it mean for a graph to have a vertex induced subgraph of P4? 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 C6 but not have a vertex induced subgraph of P4. 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 C6 as a vertex induced subgraph also has P4 as a vertex induced subgraph.