
New Member
Does graph G exist s.t. G has induced subgraph cycle C6 but no inducd sbgrph path P4?
Hello, I'm solving a problem, and I can't figure out any solution.
Can exist a graph G which has induced subgraph cycle C6 and hasn't induced subgraph path P4 ?
Thanks for any advice

Full Member
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 subforum, 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.
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules
Bookmarks