mardi 6 janvier 2015

proving that a certain graph contains a 4-cycle


I'm really bad with proofs, can someone explain/point me in the right direction on this graph?



Show that if G is a graph with |E| ≥ 2|V|^3/2, that G must contain a 4-cycle


so lets say we say V is 4, using the equation above we get E to be 16.


I drew it out and i was unable to come up with 16 edges... or am i completely misunderstanding the graph equation?





Aucun commentaire:

Enregistrer un commentaire