You are Here: Home >< Maths

# Graph theory question again. watch

1. 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?

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!
2. (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).

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?

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 constains 4 subgraphs of the form , each is a subgraph of more than one , hence this is overcounted.

I think it's easier to forget about the subgraphs and do this part from scratch.
3. (Original post by ghostwalker)

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

I think it's easier to forget about the 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
4. 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
5. (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.
6. (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.

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: January 8, 2015
Today on TSR

### The most controversial member on TSR?

Who do you think it is...

### Is confrontation required?

Discussions on TSR

• Latest
Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams

## Groups associated with this forum:

View associated groups
Discussions on TSR

• Latest

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