Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Graph theory problem

  1. Dec 10, 2007 #1
    1. The problem statement, all variables and given/known data
    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.


    2. Relevant equations



    3. 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!
     
  2. jcsd
  3. Dec 10, 2007 #2

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    Have you proven symmetry (G* is the dual of G <==> G is the dual of G*)? The solution would follow from symmetry.
     
  4. Dec 10, 2007 #3
    No, (G*)*=G is the next part of this exercise.
     
  5. Dec 11, 2007 #4

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    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)?
     
    Last edited: Dec 11, 2007
  6. Dec 11, 2007 #5
    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.
     
    Last edited: Dec 11, 2007
  7. Dec 11, 2007 #6
    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!
     
  8. Dec 13, 2007 #7
    anyone care to guide me?
     
  9. Dec 14, 2007 #8

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  10. Dec 17, 2007 #9
    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.
     
  11. Dec 18, 2007 #10

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    How many faces does the second one have? One, or more?
     
  12. Dec 18, 2007 #11
    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.
     
    Last edited: Dec 18, 2007
  13. Dec 18, 2007 #12

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  14. Dec 18, 2007 #13
    This is incorrect. The dual of the second one is one vertex with two loops. It thus has three faces.
     
  15. Dec 19, 2007 #14

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  16. Dec 19, 2007 #15
    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
     
  17. Dec 19, 2007 #16

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  18. Dec 19, 2007 #17
    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.
     
  19. Dec 19, 2007 #18

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    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 eth new edge to construct one new face, which means the extended dual has V+1 faces.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook