1. Limited time only! Sign up for a free 30min personal 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 and Function Problems

  1. Sep 22, 2015 #1


    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data
    1. Consider the Cartesian Product A X B, where A, B are finite nonempty sets, each with carnality greater than 1. There are two functions with domain A X B, called projections with mapping rules p1(a,b) = a and p2(a,b) = b. What is the target space of p1? p2? Are either of p1, 2 one to one? Onto?

    2. The star graph on n vertices has one vertex adjacent to all other vertices (and no other adjacencies). Conjecture and prove a formula for the number of edges of the star graph on n vertices.

    2. Relevant equations
    None that I can think of

    3. The attempt at a solution
    1. the target space of p1 is A
    and the target space of p2 is B. Neither are one-to-one because fixing B, there are multiple A's that could go in the first slot, but there would be the same value for p2. Same logic for p1 except fixing A.
    They're both onto, because the Cartesian product goes through each value in B, or A, and the projection takes each of those and maps it to the target space. Therefore both are onto.

    2. I don't know where to begin.
  2. jcsd
  3. Sep 22, 2015 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Your answer to 1 is correct.

    To do 2, start by drawing the star graphs on 2, 3, 4 and 5 vertices. Put the vertex that is connected to all the others at the centre, so that it looks like a star (well, the graphs with 4 and 5 vertices will. Those with 2 and 3 vertices won't). How many edges does each of those three graphs have? What is the pattern?
  4. Sep 23, 2015 #3


    User Avatar
    Homework Helper
    Gold Member

    Unusual. The only thing I found a little problematic and needing some pondering in question 2 was the word 'the'.
  5. Sep 23, 2015 #4


    User Avatar
    Gold Member

    What you found difficult or not has no concern to me.

    I will go about doing that andrewkirk, thank you!
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted

Similar Discussions: Graph Theory and Function Problems
  1. Graph Theory Problem (Replies: 0)

  2. Graph theory problem (Replies: 17)