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?

Relevance
• atsuo
Lv 6
4 weeks ago

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.