Mathematics > CHEAT SHEET > AMS303 Midterm1 Cheat Sheet | Download for quality grades | (All)

AMS303 Midterm1 Cheat Sheet | Download for quality grades |

Document Content and Description Below

Theorems: 1. Any graph, ∑deg is even. 2. Any graph, # of odd degree’s vertices is even. 3. Any graph, ∑¿ deg=∑out deg . 4. G is bipartite if and only if every cycle in G has even length. ... 5. G -> simple, (n-k) ≤ m ≤ (n-k)(n-k+1)/2. 6. G -> simple, if m ≥ (n-1)(n-2)/2, then it is connected. 7. K3,3 and K5 are non-planer. 8. G is planar if and only if it contain no sub-graph homemorphic or contractible to K3,3 and K5. 9. Euler’s Formula: n=m-f+2; f=m-n+2. 10. G -> planar, n-m+f=k+1. 11. G -> simple, connected, planar, deg ≥ 3, then m ≤ 3n-6. If in addition no triangles, m ≤ 2n-4. 12. G -> simple, planar, contains a vertex of degree at most 5. 13. G and its dual G*: n*=f, m*=m, f*=n. 14. G -> connected, planar, G** is isomorphic to G. 15. A set of edges in G forms a cycle in G is and only if the corresponding set of edges of G* forms a cutset in G*; A set of edges in G forms a cutset in G is and only if the corresponding set of edges of G* forms a cycle in G*; 16. G -> simple, largest vertex-degree Δ, then G is (Δ+1)-colorable. 17. G -> simple, connected, not complete, largest vertex-degree Δ ≥ 3, G is Δ-colorable. 18. G -> simple, planar, G is 4-colorable. 19. G -> simple, PG(k)=PG-e(k) - PG/e(k) [Show More]

Last updated: 2 years ago

Preview 1 out of 2 pages

Buy Now

Instant download

We Accept: