Graph Theory: Degree of regions in a planar graph

1.7k Views Asked by At

-Background Information:

I am studying graph theory in discrete mathematics. As I was reading my notes, I came across an example provided by my professor that I am confused about. I need some clarification to understand it better, thanks.


- Definition & Example:

enter image description here


- Question:

If I start at a vertex and an edge and go all the way to around R2 and come back, should I pass the same edge and end the same vertex? (I assume each edge that connects two components is a bridge and a bridge counts as two edges).

Could you please see my thinking section down below, am I right with the way I solved the problem?


- My thinking:

Consider each bridge to have two arrows indicating two edges.

enter image description here

In this case, I traverse 14 edges, so the degree of R4 is 14, am I right? Is this the way to do it?

If yes, why not using the other (green) edge, using that edge can give us a shorter closed walk of 12? (considering you go and come back from that edge).

enter image description here

2

There are 2 best solutions below

5
On BEST ANSWER

You need to count each edge bordering the region:

enter image description here

2
On

Yes, there are $6+4$ "normal" edges bordering $R4$ and $2$ bridges, giving $10+2\cdot 2=14$.