Results 1 to 2 of 2

Thread: Does graph G exist s.t. G has induced subgraph cycle C6 but no inducd sbgrph path P4?

  1. #1
    New Member
    Join Date
    Nov 2017
    Posts
    1

    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

  2. #2
    Full Member
    Join Date
    Mar 2016
    Posts
    839
    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.

Tags for this Thread

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •