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

Graph Theoretic Stuff

  1. Jun 21, 2013 #1
    Okay, so I just started reading a few books on Graph Theory and Topology (I wasn't sure if I should put this in Topology or here.), and I am just here to clear up some concepts, mainly about Cliques, to be precise what is a Clique? I have read Wikipedia articles and the books, and still No clear conceptual answer I am able to form. So is a Clique, like a sub graph with at least 2 vertices, or is it a sub graph that has a minimum number of vertices that are connected via an edge are at least 2?

    I am not sure If I just said the same thing twice or what D: see I am a little confused on this topic. The books I am reading are Graph Theory by Bondy and Murty, Modern Graph Theory Bollobas (his Erdos number is 2 >:3), Topology by Basener, and finally Discrete Mathematics and its Applications by Rosen. These books help with understanding some of the other technical stuff but this is Clique concept is kinda... kinda dry? you know what I mean? And since I am reading this, you better believe I am serious about this Graph Theory stuff :3
     
  2. jcsd
  3. Jun 21, 2013 #2

    lurflurf

    User Avatar
    Homework Helper

    A clique is a subset of vertices of a graph such that any to elements share an edge. If we use write ab when a and b share an edge. Suppose we have a set of vertices V then a graph G which is a subset of VxV. If U is a subset of V it is a clique if UxU is a subset of G. I know of no size restriction. The empty set and any set of one element are cliques, though uninteresting ones. In short if for all x and y in U xy is in G, U is a clique.
     
  4. Jun 21, 2013 #3
    So, like a maximally complete sub graph or something?
     
  5. Jun 21, 2013 #4

    lurflurf

    User Avatar
    Homework Helper

    I guess you could say that. Any complete subgraph is a clique so maximally complete sub graph and maximal clique are equivalent.
     
  6. Jun 21, 2013 #5
    oh okay thank you so much, also one more thing say there is a graph with 5 edges does that mean it has 5 1-vertex Cliques and 1 5-vertex Clique?
     
  7. Jun 22, 2013 #6

    lurflurf

    User Avatar
    Homework Helper

    How many vertices? Remember since a clique is a complete subgraph if it has n vertices it must have n(n-1)/2 edges. No clique can have 5 edges as a clique has a triangle number of edges
    0,1,3,6,10,15,...
     
  8. Jun 22, 2013 #7
    so if we were to work with ##K_{5}## where it has a vertex sex of 5 elements ## \left(v_{1}, v_{2}, v_{3}, v_{4}, v_{5} \right)## then a clique is a sub vertex set such that it contains ##\left( ^{6} _{2}\right) ## vertices? n is that what you are getting at?
     
  9. Jun 22, 2013 #8

    lurflurf

    User Avatar
    Homework Helper

    Are you mixing up vertices and edges?

    A clique with n vertices has edges=n(n-1)/2=n choose 2=[itex]n \choose 2[/itex]

    Supposing your K5 is complete we have the following cliques
    1 5-vertices cliques (10 edges)
    5 4-vertices cliques ( 6 edges)
    10 3-vertices cliques ( 3 edges)
    10 2-vertices cliques ( 1 edges)
    5 1-vertices cliques ( 1 edges)
    1 0-vertices cliques ( 0 edges)

    Kn if complete has cliques
    [itex]n \choose k[/itex] k-vertices cliques ([itex]k \choose 2[/itex] edges)

    if we were to work with ##K_{n}## where it has a vertex sex of n elements ## \left(v_{1}, v_{2}, v_{3}, v_{4}, v_{5},... \right)## then a clique is a sub vertex set such that it contains k vertices and ##\left( ^{k} _{2}\right) ## eges
     
  10. Jun 22, 2013 #9
    But ##\left( ^{n} _ {2}\right) = n^{2}-n## and triangle numbers are ##\left(^{n+1} _{2}\right)## but all of the rest of the stuff I seem to understand, so you are saying that the number of k-vertices are just the binomial formula, gotcha!
     
  11. Jun 22, 2013 #10

    lurflurf

    User Avatar
    Homework Helper

    [itex]{n \choose 2} =\frac{n!}{2!(n-2)!)}=n(n-1)/2[/itex]
     
    Last edited: Jun 22, 2013
  12. Jun 22, 2013 #11
    What do you mean? they don't really seem like they are the same.
     
  13. Jun 22, 2013 #12

    lurflurf

    User Avatar
    Homework Helper

    They are [itex]{n \choose 2} \, \mathop{and} \, {{n+1} \choose 2}[/itex] they are the same numbers shifted by one.


    0,1,3,6,10,15,...
    1,3,6,10,15,21,...
     
  14. Jun 22, 2013 #13
    But ## n^2-n \neq (n^2-n)/2## I still don't understand how they come from that.
     
  15. Jun 22, 2013 #14

    lurflurf

    User Avatar
    Homework Helper

    [itex]{n \choose 2} =\frac{n!}{2!(n-2)!)}=n(n-1)/2[/itex]
    you have lost a 2

    Just draw out a few small graphs it will become clear.
     
  16. Jun 22, 2013 #15
    I see never mind, I was thinking of permutations, and not combinations D: thank you for you help!!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Graph Theoretic Stuff
  1. Algebra II stuff (Replies: 4)

  2. Math olympiad stuff (Replies: 2)

Loading...