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 this document to get the full access instantly
Instant Download Access after purchase
Buy NowInstant download
We Accept:
Reviews( 0 )
$2.00
Can't find what you want? Try our AI powered Search
Document information
Connected school, study & course
About the document
Uploaded On
Feb 12, 2023
Number of pages
2
Written in
Additional information
This document has been written for:
Uploaded
Feb 12, 2023
Downloads
0
Views
93
.png)
