Anonymous
Anonymous asked in Science & MathematicsMathematics · 1 month ago

Discrete Math - Consider a graph with a loop, and one without a loop... ?

Consider a graph with a loop, and one without a loop. From the following, choose a relevant strategy:

(a) Work Backwards

(b) Use a Formula

(c) Use Process of Elimination

Using your strategy, show whether any two graphs with degree sequence 3,2,1 are isomorphic. Why did you choose this strategy?

1 Answer

Relevance
  • atsuo
    Lv 6
    4 weeks ago
    Favourite answer

    I do not understand about the strategy, sorry.

    Let G be the graph whose degree sequence is 3,2,1.

    G has 3 vertices, so let v3,v2,v1 be vertices whose degrees are 3,2,1.

    The sum of the degrees is 6, so G has 3 edges.

    The degree of v1 is 1, so exactly one edge e(v1,v2) or e(v1,v3) must exist.

    Case1. When e(v1,v2) exists

    One edge e(v2,v3) and one loop e(v3,v3) exist.

    Case2. When e(v1,v3) exists

    There are two sub-cases :

    Case2-1. Multiple edges e(v2,v3) and e(v2,v3) exist.

    Case2-2. Two loops e(v2,v2) and e(v3,v3) exist.

    Case1 has one loop, case2-1 has no loop and case2-2 has two loops.

    So if G has no loop then any two graphs with degree sequence 3,2,1 are isomorphic.

    If G has exactly one loop then any two graphs with degree sequence 3,2,1 are isomorphic.

    If G has exactly two loops then any two graphs with degree sequence 3,2,1 are isomorphic.

Still have questions? Get answers by asking now.