Hey there! Sign in to join this conversationNew here? Join for free
    • Thread Starter
    Offline

    9
    ReputationRep:
    Can someone check these (bit skeptical of my answers).

    a) How many copies of C_4 in K_n?

    Picking any 4 vertices can be used to give a copy of C_4 of each of these there are 4! ways in which the vertices can be arranged but this overcounts by a factor of 8 (4 vertices*2 directions that can be transversed) so the total is (4!/8)*nC4=3(nC4).

    b) How many copies of P_3 in K_n?

    Any 4 vertices choose represent 4C3=4paths so we have 4(nC4) in total.

    How can the answer to a be smaller than the answer to b when we have that every P_3 in K_n is contained within a C_4 in K_n?

    No idea about this part any help?

    Thanks!

    Sorry about no latex I was rushing to type this.

    If it's wrong could you explain why and point me in the right direction I will check on this thread in an hour or so thanks!
    • Study Helper
    Online

    13
    Study Helper
    (Original post by poorform)
    Can someone check these (bit skeptical of my answers).

    a) How many copies of C_4 in K_n?

    Picking any 4 vertices can be used to give a copy of C_4 of each of these there are 4! ways in which the vertices can be arranged but this overcounts by a factor of 8 (4 vertices*2 directions that can be transversed) so the total is (4!/8)*nC4=3(nC4).

    Agree with the final answer.

    b) How many copies of P_3 in K_n?

    Any 4 vertices choose represent 4C3=4paths so we have 4(nC4) in total.

    How can the answer to a be smaller than the answer to b when we have that every P_3 in K_n is contained within a C_4 in K_n?

    No idea about this part any help?

    Thanks!

    Sorry about no latex I was rushing to type this.

    If it's wrong could you explain why and point me in the right direction I will check on this thread in an hour or so thanks!
    Although a particular C_4 constains 4 subgraphs of the form P_3, each P_3 is a subgraph of more than one C_4, hence this is overcounted.

    I think it's easier to forget about the C_4 subgraphs and do this part from scratch.
    • Thread Starter
    Offline

    9
    ReputationRep:
    (Original post by ghostwalker)
    Agree with the final answer.



    Although a particular C_4 constains 4 subgraphs of the form P_3, each P_3 is a subgraph of more than one C_4, hence this is overcounted.

    I think it's easier to forget about the C_4 subgraphs and do this part from scratch.
    I get the first part then any chance you could explain the method for the second question in a bit more detail.

    As for the last question I just said that even though each P_3 is contained in C_4 within K_n we have that there are 4 P_3's in each C_4 in K_n so obviously this number should be bigger.

    Is this right? If not could you tell me why and help me understand the right way to do it.

    Thanks
    • Thread Starter
    Offline

    9
    ReputationRep:
    btw I forgot to mention I'm not sure if my definitions for K,P,C are different.

    e.g.

    K_5=5 vertices each connected to each other

    P_5=6 vertices with each vertex connected to the next one (i,i+1) so there will be 5 edges.

    and

    C_5=5 vertices and edges with the last vertex joined to the first one.

    cheers
    • Study Helper
    Online

    13
    Study Helper
    (Original post by poorform)

    P_5=6 vertices with each vertex connected to the next one (i,i+1) so there will be 5 edges.
    Must have got my wires crossed: I was assuming P_n had n vertices.

    In that case, ignore what I said about part b).

    b) Each C_4 has 4 P_3 subgraphs, and each P_3 belongs to only 1 C_4.

    Hence there are 4 x [3(nC4)] P_3 subgraphs.

    Alternatively, there are nC4 ways to choose the four vertices, and 4! orderings of which can be considered in pairs, e.g the vertex sequence a,b,c,d is gives the same graph as d,c,b,a. So divide by 2, giving the same result as previous - in bold.

    Your answer to the final part looks fine - it's linking the C_4 to the P_3 subgraphs that is the important bit, IMO.
    • Thread Starter
    Offline

    9
    ReputationRep:
    (Original post by ghostwalker)
    Must have got my wires crossed: I was assuming P_n had n vertices.

    In that case, ignore what I said about part b).

    b) Each C_4 has 4 P_3 subgraphs, and each P_3 belongs to only 1 C_4.

    Hence there are 4 x [3(nC4)] P_3 subgraphs.

    Alternatively, there are nC4 ways to choose the four vertices, and 4! orderings of which can be considered in pairs, e.g the vertex sequence a,b,c,d is gives the same graph as d,c,b,a. So divide by 2, giving the same result as previous - in bold.

    Your answer to the final part looks fine - it's linking the C_4 to the P_3 subgraphs that is the important bit, IMO.
    Thanks I did figure out it was 12*(nC4) by using the second method last night but thanks for the help and confirmation I would rep but it won't let me thanks though.
 
 
 
Poll
Do you agree with the PM's proposal to cut tuition fees for some courses?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.