1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Graph theory problem
  1. Graph Theory problems (Replies: 8)

  2. Graph Theory Problem (Replies: 0)

Loading...