Exam questions Flashcards
Just knowing which one is it and how it is proven. :)
Theorem 1.1**
For any graph G: the sum of the vertex degrees is equal to the double number of edges.
The Principal Theorem of Graph Theory
The sum of the entries in the row corresponding to vertex v is exactly d(v). But each of the m column sums of incidence matrix M is 2, each edge having two ends, thus being counted twice in the first sum.
Double counting; incidence matrix
Theorem 2.1**
Let G be a graph in which all vertices have degree of at least two. Then G contains a cycle.
If G has a loop, it contains a cycle of length 1; if it has parallel edges, it contains a cycle of length 2. So we may assume that G is simple.
Let P := v0v1…vk-1vk be the longest path in G. Because the degree of vk is at least two, it has a neighbour v different from vk-1. If v is not on a path, a contradiction, because the chosen path P is not the longest. Therefore, v = vi, for some 0 <= i <= k-2, and vivi+1…vkvi is a cycle in G.
Constructive; the longest path; contradiction
Theorem 2.2**
Any simple graph G with sum (d(v) over 2) > (n over 2) contains a quadriliteral.
Denote by p2 the number of paths of length 2 in G, and by p2(v) the number of such paths whose central vertex is v. Clearly, p2(v) = (d(v) over 2). As each path of length 2 has a unique central vertex, p2 = sum (p2(v)) = sum (d(v) over 2). On the other hand, each such path also has a unique pair of ends. Therefore, the set of all paths of length two can be partitioned into (n over 2) subsets according to their ends. The hypothesis sum (d(v) over 2) > (n over 2) now implies, by virtue of Pigeonhole Principle, that one of these subsets contains two or more paths; that is, there exist two paths of length two with the same pair of ends. The union of these paths is a quadriliteral.
Double counting; Pigeonhole Principle
Theorem 2.3
Every tournament has a directed Hamilton path
Redei’s Theorem
Use the book
Mathematical induction; 3 cases!!!
Theorem 2.4
Every loopless graph G contains a spanning bipartite subgraph F such that d(v) in F >= 1/2 d(v) in G, for all v in V.
Use the book
Contradiction; switching vertices between parts
Theorem 2.5**
Every graph with average degree at least 2k, where k is a positive integer, has an induced subgraph with minimum degree at least k+1.
Let G be a graph with average degree d(G) >= 2k, and let F be an induced subgraph of G with the largest possible average degree and, subject to this, the smallest number of vertices. We show that δ(F) >= k+1. This is clearly true if v(F) = 1, since then δ(F) = d(F) >= d(G), by the choice of F. We may therefore assume that v(F) > 1. Suppose, by contradiction, that d(v) <= k in F, for some vertex v of F. Consider the vertex-deleted subgraph F’ := F - v. Note that F’ is also an induced subgraph of G. Moreover, d(F’) = … = d(F), because v(F’) < v(F), this contradicts the choice of F. Therefore, δ(F) >= k + 1.
Contradiction
Theorem 2.7**
A graph admits a cycle decomposition iff it is even.
[=>] If a graph has a cycle decomposition C, the degree of each vertex is twice the number of cycles of C to which it belongs, so it is even.
[<=] Suppose that G is even. If G is empty, then E(G) is decomposed by the empty family of cycles. If not, consider the subgraph F of G induced by its vertices of positive degree. Because G is even, F is also even, so every vertex of F has degree of at least two. By Theorem 2.1, F contains a cycle C. The subgraph G’ := G\E(C) is even and has fewer edges than G. By induction, G’ has a cycle decomposition C’. Therefore, G has the cycle decomposition C := C’ U {C}.
Induction; subgraph; Theorem 2.1; cycle decomposition definition
