Results 1 to 11 of 11

Math Help - question in math logic

  1. #1
    Junior Member
    Joined
    Jan 2011
    Posts
    46

    question in math logic

    If we have K_n denote the complete graph on n vertices, can any one explain to me how to know how many substructures does K_n have?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,383
    Thanks
    1474
    Awards
    1
    Quote Originally Posted by Mike12 View Post
    If we have K_n denote the complete graph on n vertices, can any one explain to me how to know how many substructures does K_n have?
    What do you mean by substructure?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jan 2011
    Posts
    46
    If B is a set, then A ⊂ B means that A is a subset of B.
    If N is a structure, then M ⊂ N means that M is a substructure of N.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,383
    Thanks
    1474
    Awards
    1
    Quote Originally Posted by Mike12 View Post
    If B is a set, then A ⊂ B means that A is a subset of B.
    If N is a structure, then M ⊂ N means that M is a substructure of N.
    So in this context, a substructure would be a subgraph of \mathcal{K}_n~?.

    Are these labeled or unlabeled graphs?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jan 2011
    Posts
    46
    there is no thing about labeled or unlabeled graph , all what I have in the question is a complete graph
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    If N is a structure, then M ⊂ N means that M is a substructure of N.
    And what does ⊂ mean when applied to two structures? After all, structures are not just sets; they are tuples consisting of the domain together with functions and/or relations. Therefore, the regular concept of set inclusion cannot be applied to structures, and a specific definition is needed.

    According to Wikipedia, M is a substructure of N if the domain of M is a subset of the domain of N and the relations of M are the corresponding relations of N restricted to the domain of M. A subgraph is a not necessarily a substructure because it may fewer edges than what is inherited from the large graph. Subgraphs are called weak substructures. So, a relevant question about this problem is, are we talking about regular or weak substructures? Or what is the definition of a substructure?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Jan 2011
    Posts
    46
    I think in this question it means subgraph
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,383
    Thanks
    1474
    Awards
    1
    Quote Originally Posted by Mike12 View Post
    I think in this question it means subgraph
    If we have N vertices then \mathcal{K}_N has \dbinom{N}{2} edges.

    There are \displaystyle 2^{\binom{N}{2}} possible subgraphs of \mathcal{K}_N.
    (That counts the empty-edge subgraph).

    Would tell us what textbook you are following?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Jan 2011
    Posts
    46
    It is (mathematical logic) , so you told me that there are two to the power N choose 2 possible subgraphs.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,383
    Thanks
    1474
    Awards
    1
    Quote Originally Posted by Mike12 View Post
    It is (mathematical logic) , so you told me that there are two to the power N choose 2 possible subgraphs.
    I answered a Graph Theory problem.
    I have no idea how that relates to mathematical logic. You seem to refuse to answer a simple question about the text material. If you tell us about the textbook, one of us may have a better idea as to what you are doing. Until then, I done with it.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Jan 2011
    Posts
    46
    sorry but I do not refuse to answer you about textbook , the text book is ( Mathematical logic).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mainly logic with a little math
    Posted in the Algebra Forum
    Replies: 3
    Last Post: March 25th 2009, 06:48 AM
  2. discrete math help logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 23rd 2009, 05:27 AM
  3. math logic problem??
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: October 14th 2007, 07:08 PM
  4. math logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 3rd 2007, 05:28 AM
  5. Discrete math logic
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 12th 2007, 02:04 PM

Search Tags


/mathhelpforum @mathhelpforum