Question

Prove i.) The line graph of Pn is Pn-1 ii.) The line graph of Cn is...

Prove

i.) The line graph of Pn is Pn-1

ii.) The line graph of Cn is Cn

Homework Answers

Answer #1

i) No. of edges in Pn is n. Hence L(Pn) has n-1 vertices.Name them 1,2,..,n-1. edges i and i+1 have common point hence in L(Pn) vertices i and i+1 are adjacent and so it is isomorphic to P(n-1)

ii) Consider a cycle with n vertices, it has n edges in its path. By these edges as vertices in L(Cn), we form a cycle with n edges. This implies that, both Cn and L(Cn) has same number of vertices and edges and also have the same degree sequence. So, there exists a 1-1 correspondence between V(Cn) into V(L(Cn)) and E(Cn) and E( L(Cn)) and preserves adjacency

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
. Prove that, for all integers n ≥ 1, Pn i=1 i(i!) = (n + 1)!...
. Prove that, for all integers n ≥ 1, Pn i=1 i(i!) = (n + 1)! − 1
Exercise 3. Let Wn be the graph obtained from the cycle graph Cn by adding one...
Exercise 3. Let Wn be the graph obtained from the cycle graph Cn by adding one new vertex which is adjacent to every vertex of Cn. Prove that for n ≥ 3, Wn does not have an Eulerian trail.
LED (PN junctions): if you have a graph of V (x-axis) vs ln(I) (y-axis), how do...
LED (PN junctions): if you have a graph of V (x-axis) vs ln(I) (y-axis), how do you calculate Vt (thermal voltage) and Is (saturation current)? While plotting the graph, do you take ln of the current in amps or mA?
show that product graph K4 X Pn is graceful labelling
show that product graph K4 X Pn is graceful labelling
Graph a monopolistically competitive firm in both (i) SR, and (ii) LR.
Graph a monopolistically competitive firm in both (i) SR, and (ii) LR.
(i)Prove that if ∀a∈A ∃b∈B s.t. a≤b, then supA≤supB. (ii)Prove that if ∀a∈A ∃b∈B s.t. a≥b,...
(i)Prove that if ∀a∈A ∃b∈B s.t. a≤b, then supA≤supB. (ii)Prove that if ∀a∈A ∃b∈B s.t. a≥b, then infB≤infA
Potassium hexachloroferrate(II) can be dissolved in water and reacted with cyanide ion (CN-) to form the...
Potassium hexachloroferrate(II) can be dissolved in water and reacted with cyanide ion (CN-) to form the more favorable cyano-complex forms: K4[FeCl6] + 6 CN- ===> K4[Fe(CN)6] + 6 Cl- A student performs this experiment by adding 20 mL of 4.0 M NaCN (aq) to 4.562 g of K4[FeCl6]. The solid product was isolated, dried, and massed. Answer the following questions based on this information. 1. How many moles of potassium hexachloroferrate(II) are available at the start? 2. How many moles...
Graph G is a connected planar graph with 1 face. If G is finite, prove that...
Graph G is a connected planar graph with 1 face. If G is finite, prove that there is a vertex with degree 1.
Consider a population that grows according to the recursive rule Pn=Pn−1+90Pn=Pn-1+90, with initial population P0=50 P0=50....
Consider a population that grows according to the recursive rule Pn=Pn−1+90Pn=Pn-1+90, with initial population P0=50 P0=50. Then: P1 = P2 = Find an explicit formula for the population. Your formula should involve nn (use lowercase n) Pn= Pn=     Use your explicit formula to find P100 P100 =
Construct a type-II pn heterojunction and schematically draw its band diagrams in both charge neutral and...
Construct a type-II pn heterojunction and schematically draw its band diagrams in both charge neutral and equilibrium conditions
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT