Proofs Flashcards
G is Eulerian IFF G is even and has at most 1 non-trivial component. (maximality)
T is a maximal trail. It is closed (if not, endpoints have odd degree, and must have another edge contradicting max). E(T) = E(G), otherwise, we can start from e’ (the missed edge) and then go around T, making a larger trail, contradicting maximality.
Every loopless graph has a bipartite subgraph with at least e(G)/2 edges.
Take any partition X,Y. If v has more neighbors in X then in Y, move it to Y. Repeat then delete all edges within X and Y.
e is a cut-edge IFF e belongs to no cycle
**Prove H-e is connected IFF e is in a cycle since deleting e doesn’t affect any other component in G
=> if H-e is connected, and xy = e, H-e has an x,y path. Add e back and you get a cycle
<= if xy = e is in a cycle, there is an x,y path P not containing e. H-e is connected since you can replace e with P in every u,v path containing e.
Every tree on at least 2 vertices has at least 2 leaves (maximality)
**if you delete a leaf from an n vertex tree, you get a n-1 vertex tree.
Consider a Path in T with as many edges as possible with u,v as its endpoints. All neighbors of u,v are on P by maximality, and any edge not on P would make a cycle by maximality. so d(u) = d(v) = 1.
If T is a tree w/ k edges, and G is a simple graph where every vertex has degree at least k, then G has a copy of T as a subgraph. (induction on k, leaf removal)
K = 0 obvious. For K >0, let v be a leaf. By hypothesis, G has T-v as a subgraph T’. Let u be the vertex of G that is the neighbor of v. d(u) is at least k and has at most k-1 neighbors in T’ (since T’ has k-1 edges, resulting in k vertices). Thus u must have a neighborhood outside of T’ and T’ + uv is the desired copy of T.
If M and M’ are matchings, F = M Δ M’ consists of even cycles and alternating paths
Each vertex is incident with at most 1 edge in M and 1 in M’ so the max degree of any vertex in F is 2. Thus the components of F are cycles and paths that alternate between M and M’.
Every k-regular bipartite graph has a perfect matching
k|X| = e(G) = k|Y| so |x| = |y|. Thus a matching saturating X must be a perfect matching. So we verify Hall’s condition and are done.
α’(G) + β’(G) = n(G) (Gallai)
Let M be a max matching and obtain an edge cover L by adding an edge incident with each unsaturated vertex. Thus β’(G)≤ |L| = |M| + (n - 2|M|) = n - |M| = n - α’(G).
Consider a min edge cover L. The spanning subgraph H with e(H) = L has no 2 vertices u,v of degree bigger than 2 since L-uv would be a smaller cover. Thus the q components of H are stars. Pick one edge from each star to form a matching M. α’(G) ≥ |M| = q = n - |L| = n - β’(G)
κ(G) ≤ κ’(G) ≤ δ(G) (whitney’s)
-The edges incident with a vertex of minimum degree form an edge cut, so the second inequality holds
Now let |[S,S_]| = κ’(G)
-If every vertex in S is adjacent to every vertex in S comp, then |[s, s_]| ≥ |s| |s_| ≥ n(G) - 1 ≥ κ(G).
-Suppose there is an x in S and y in S_ with no edge xy. let T be the set of all neighbors of x in S_ and the rest of the vertices in S that have neighbors in S_. T is a vertex cut since every x,y path must go through T, since we either go from x to S_ or from a different vertex in S with a neighbor in S_ to get to y. So κ(G) ≤ |T|. Also κ’(G) = |[S, S_]| ≥ |T| since every vertex in T can be associated with a distinct edge in [S, S_]
If Δ(G) ≤ 3, then κ(G) = κ’(G).
κ(G) ≤ κ’(G) by Whitney’s
Let S be a min size vertex cut. Let H and J be components of G - S. Each vertex in S must have neighbors in H and J and for all of those vertices have exactly one neighbor in either H or J. If you remove these edges, it disconnects the graph. Unless some of these vertices are connected, in which case they can only have one neighbor in H and J. So just remove the edges from those vertices to either H or J. so κ’(G) ≤
S|= κ(G).
Whitney’s 2-Connected Theorem (A graph on at least 3 vertices is 2-connected IFF for all uv there are 2 internally disjoint uv paths)
induction on distance of shortest uv path Base d(u,v) = 1 uv is an edge and is therefore one path. Since 2 = κ(G) ≤ κ'(G), G - uv is still connected and must have a second uv path (internally disjoint from the first) Inductive step d(u,v) > 1 Let w be the vertex before v on the shortest uv path so d(uw) = k-1. By hypothesis we have 2 internally disjoint uw paths P and Q. If v is in P or Q, then the cycle P U Q contains our desired paths. Otherwise, G - w is connected since κ(G) = 2, so G - w has a uv path R. if R is internally disjoint from P or U then we are done. Otherwise let Z be the last vertex on R that meets Q WLOG. then uPwv and uQzRv are the desired paths
κ(G-xy) ≥ κ(G) - 1
κ(G-xy) ≤ κ(G) and equality holds unless G-xy has a separating set S that does not separate G, with |S| = κ(G-xy). Since G - S is connected, but G - S - xy is not it follows that xy is a cut edge in G-S and G-xy-S has 2 components. WLOG, if |X| ≥ 2, then X is a cut vertex in G - S, and S U x is a vertex cut of G with size κ(G-xy) + 1. So κ(G-xy) + 1 ≥ κ(G)
if |x| and |y| is 1, then k(G - xy) = n - 2 and if k(G-xy) < k(G), then n-2 = k(G-xy) < k(G) ≤ δ(G) ≤ n-1. so δ(G) = n-1 and thus G = Kn and the result holds by inspection.
Dirac Fan Lemma (G is k connected IFF for every x and U of at least k vertices there is an xU fan of size k.
(=>) Create a vertex y adjacent to all of U. By expansion lemma, G + y is k-connected. so there are k internally disjoint x,y paths which yields an x,u fan
(=>)
If G is bipartite, x’(G) = Δ(G)
G IS K-REGULAR
induction on k
k = 0, has no edges so requires 0 colors
k > 0, since G is bipartite G has a perfect matching. G - M is (k-1) regular and by hypothesis can be k-1 colored. Give edges in M color k.
G IS NOT K REGULAR
Add vertices to the smaller partition until they are of the same size. Since Σd(x) = Σd(y), if x has d(x) < k = Δ, then the same goes for some y. add xy. repeat until G is regular. Apply case 1.
