Graph Theory Problem: Proving Dual Graph Faces Contain 1 Vertex

[ehrenfest]

Homework Statement

http://en.wikipedia.org/wiki/Dual_graph
I am trying to show that if a graph G is connected, then each face of its dual graph G* contains exactly one vertex of G.

Homework Equations

The Attempt at a Solution

I tried counting the vertices in G and the faces in G*. I drew enough counterexample to see that if G has two components, then one face contains two vertices of G. My mind just gets tangled when I try to visualize this!

 

[EnumaElish]

Have you proven symmetry (G* is the dual of G <==> G is the dual of G*)? The solution would follow from symmetry.

 

[ehrenfest]

No, (G*)*=G is the next part of this exercise.

 

[EnumaElish]

A dual graph of a given planar graph G:
1. has a vertex for each plane region of G, and
2. an edge for each edge joining two neighboring regions.

Suppose G* satisfies 1 and 2, but some face of G*:
a. contains no vertex of G, or
b. contains k > 1 vertices of G.

Can you show a contradiction in either case (because G is connected)?

 

[ehrenfest]

a)
let f be a face of G* that contains no vertex of G
let uv be an edge on the boundary of G*
u and v are faces in G whose boundaries share an edge e in G
I want to say that one endpoint of e must lie in f, but I just cannot figure out how to say that mathematically.

Wait. Vertex u is contained in a face f_1 of G and vertex v is contained in a face f_2 of G and e is an edge on the boundary of each of these faces. Somehow, e must go from f_1 to f_2. Therefore, e must cross some edge e_1 on the boundary of both f_1 and f_2.

Let \alpha be a bijection that maps edges in G to edges in G* s.t. if e in G is on the boundary of f_1 and f_2, then \alpha(e) connects the vertices f_1 and f_2 in G*.

\alpha(e_1) connects u and v in G*

Hmm. I thought this would be easy. I'll work on this more later.

 

[ehrenfest]

a)

Let \alpha be a bijection that maps edges in G to edges in G* s.t if e is on the boundary of f_1 and f_2, then \alpha(e) connects the vertices f_1 and f_2 in G*.

Let f be a face of G* that contains no vertex of G. Let f_1 f_2 be an edge on the boundary of G*. By the definition of a dual graph, f_1 and f_2 represent faces of G that that share a boundary edge in G. Now the edge f_1 f_2 MUST cross an edge of G on the boundary between the faces of f_1 and f_2. Call this edge e.

Gosh. This proof is KILLING ME. Please help!

 

[ehrenfest]

anyone care to guide me?

 

[EnumaElish]

I did not study graph theory, so I have this question: is the following graph connected?

X---------------X

How about this:

X-----X-------X ?

What is the dual in each case?

 

[ehrenfest]

They are both connected. The first one is the same as its dual. The dual of the second one is just two vertices with 2 edges between them.

 

[EnumaElish]

The dual of the second one is just two vertices with 2 edges between them.

How many faces does the second one have? One, or more?

 

[ehrenfest]

The second one has one (infinite) face.

The dual of the second one has two (one infinite and one finite) faces.

EDIT: The second sentence is wrong.

 

[EnumaElish]

Doesn't this contradict what you are asked to prove? You've found a connected graph with 3 vertices "X", whose dual has 2 vertices "*" with 2 edges "(" and ")" -- see below:

*
(X)----------X-----------X
*
One face of the dual graph contains two of the original vertices.

 

[ehrenfest]

They are both connected. The first one is the same as its dual. The dual of the second one is just two vertices with 2 edges between them.

This is incorrect. The dual of the second one is one vertex with two loops. It thus has three faces.

 

[EnumaElish]

I see. Let's walk through how the dual is constructed:
1. put a vertex * on each original face
2. wrap edges around each original vertex X (this somehow gives you the exact number of edges as the original)
[3. add another vertex onto an original face.]

You need to prove that step [3] is superfluous/unnecessary, correct?

 

[ehrenfest]

Step 1 is right. I am not sure what you mean in step 2 by "wrapping edges around each original vertex". See wikipedia for the definition and some examples:

http://en.wikipedia.org/wiki/Dual_graph

 

[EnumaElish]

Another question

Suppose I have X----X

I want to add another vertex and preserve connectedness. What dictates how many edges that the extended graph will have?

I know I can preserve connectedness with 1 more edge, as in X----X-----X, but is there anything that says I cannot add two new edges: X----X===X ?

In the latter case, what is the dual?

 

[ehrenfest]

Connectedness only means that there is some path between every pair vertices. So yes, if you have a connected graph, you can add edges between two vertices and preserve connectedness.

Its really hard to draw graphs like this. What is shown below is not what I typed in because html is messing up the spacing. Hit the quote button to see the graph that I meant to draw.X------X-------X
2 | 1 |
----------

I reproduced the graph that you drew and put in ONLY THE VERTICES, 1 and 2, of the dual. Vertex 1 is connected to vertex 2 with 2 edges, and vertex 2 is connected to itself with a loop.

 

[EnumaElish]

Connectedness only means that there is some path between every pair vertices. So yes, if you have a connected graph, you can add edges between two vertices and preserve connectedness.

Its really hard to draw graphs like this. What is shown below is not what I typed in because html is messing up the spacing. Hit the quote button to see the graph that I meant to draw.


X------X-------X
2 | 1 |
----------

I reproduced the graph that you drew and put in ONLY THE VERTICES, 1 and 2, of the dual. Vertex 1 is connected to vertex 2 with 2 edges, and vertex 2 is connected to itself with a loop.

I think I have an inelegant proof by induction.

Suppose the original connected graph has V vertices, E edges and F faces. Suppose the statement is true for graph G(V, E, F). This has dual G*(F, E, V) [which is also connected].

Now add a new vertex and e new edges, which create f new faces. Suppose G(V+1, E+e, F+f) is also connected.

"Clearly," f < e. I will assume f = e - 1, but this needs to be proved. Given the narrow graph G(V, E, F) is connected, e - 1 of the new edges encircle (form) the f new faces.

By def., the dual of the extended graph has F+f vertices and E+e edges; it needs to be shown that it has V+1 faces and we're done.

The narrow dual had V faces. In the extended dual, use e - 1 edges to connect the f new vertices to each other, and use the e^th new edge to construct one new face, which means the extended dual has V+1 faces.