Graph Theory Exam 2 (to share)

Exam 2 xd 2.20, 2.21, 2.22, 2.25, 2.26, 2.27, 2.28, 3.5 (any full proof is ok), 3.8, 4.1, 4.2, 4.3, 4.5, 4.6, 4.7, 4.8, 4.10, 4.11. 4.12, 5.1, 6.10

Kelly’s Lemma 2.20: For any two graphs F and G such that v(F) < v(G), the parameter (G choose F) is reconstructible.

Each copy of F in G occurs in exactly v(G) − v(F) of the vertex-deleted subgraphs G − v (namely, whenever the vertex v is not present in the copy). Therefore, $\binom{G}{F}$ $=\frac{1}{\nu(G) - \nu(F)}\sum_{v\in V}\binom{G-v}{F}$ . Right hand side is constructible, so is left side.

Corollary 2.21: For any two graphs F and G such that v(F) < v(G), the number of subgraphs of G that are isomorphic to F and include a given vertex v is

reconstructible.

See 2.20 (Kelly’s Lemma) given $\binom{G}{F}-\binom{G-v}{F}$ .

“Each copy of F in G occurs in exactly v(G) − v(F) of the vertex-deleted subgraphs G − v (namely, whenever the vertex v is not present in the copy). Therefore, $\binom{G}{F}$ $=\frac{1}{\nu(G) - \nu(F)}\sum_{v\in V}\binom{G-v}{F}$ . Right hand side is constructible, so is left side.“

Solving this, total copies of F in G is reconstructible (kelly’s), so is F in G-v (G-v from the card in deck). So, as both are reconstructible, the difference is as well.

Corollary 2.22: The size and the degree sequence are reconstructible parameters

Take F = K₂ in Kelly’s Lemma and Corollary 2.21, respectively.

2.21: (Kelly’s Lemma) given $\binom{G}{F}-\binom{G-v}{F}$ .

2.20: “Each copy of F in G occurs in exactly v(G) − v(F) of the vertex-deleted subgraphs G − v (namely, whenever the vertex v is not present in the copy). Therefore, $\binom{G}{F}$ $=\frac{1}{\nu(G) - \nu(F)}\sum_{v\in V}\binom{G-v}{F}$ . Right hand side is constructible, so is left side.“

Set F - K2. In Kelly’s Lemma, copies of K2 in G is the number of edges.

F = K2 in 2.21, number of edges through a specific vertex v is the degree. You can recover the deleted vertex’s degree for each vertex, so you can reconstruct the full degree sequence.

Theorem 2.25: Mobius Inversion Formula. Let f : 2^T → ℝ be a function on subsets of a finite set T. Define $g(S) = \sum_{S \subseteq X \subseteq T} f(X)$ . Then you can invert this: $f(S) = \sum_{S \subseteq X \subseteq T} (-1)^{|X| - |S|} \, g(X)$

For the other proofs based on this, you can think of it as changing the function values with the -1 to the whatever power. For this proof dont die.

By the binomial theorem, $\sum_{S\subseteq X\subseteq Y}(-1)^{|X|-|S|}=\sum_{\left|S\right|\le\left|X\right|\le\left|Y\right|}\binom{|Y|-|S|}{|X|-|S|}(-1)^{|X|-|S|}=(1-1)^{|Y|-|S|}$

which equals 0 if S⊂Y and 1 if S=Y. Therefore:
$f(S) = \sum_{S \subseteq Y \subseteq T} f(Y) \sum_{S \subseteq X \subseteq Y} (-1)^{|X|-|S|} = \sum_{S \subseteq X \subseteq T} (-1)^{|X|-|S|} \sum_{X \subseteq Y \subseteq T} f(Y) = \sum_{S \subseteq X \subseteq T} (-1)^{|X|-|S|} \, g(X)$

In my terms, memorize this. Step by step, take the larger set (Y), subtract S, and do the same for X. Invert it, change the summation, then you get 1-1 to the Y - S.

Just memorize this noob.

Lemma 2.26 Nash-Williams’ Lemma Let G be a graph, F a spanning subgraph of G, and H an edge reconstruction of G that is not isomorphic to G. Then,
$|G \to G|_F - |G \to H|_F = (-1)^{e(G)-e(F)} \cdot \operatorname{aut}(G)$

You need to have these two givens from Mobius Inversion FUN:
2.6: $\sum_{F \subseteq X \subseteq G} |G \to H|_X = |F \to H|$

2.7: $|F \to H| = \operatorname{aut}(F) \binom{H}{F}$

For 2.6, partitions embeddings of F into H by how much of G they preserve. Each embedding of F into H extends to preserve some maximal subgraph X between F and G. So summing over all possible X recovers the total

2.7 counts the labeled embeddings of F into H: each unlabeled copy of F in H can be reached by aut(F) permutations

Then, through them, you get
$\sum_{F \subseteq X \subseteq G} |G \to H|_X = \operatorname{aut}(F) \binom{H}{F}$

Mobius, you get:

$$|G \to H|_F = \sum_{F \subseteq X \subseteq G} (-1)^{e(X)-e(F)} \operatorname{aut}(X) \binom{H}{X}$$

Therefore,

$$|G \to G|_F - |G \to H|_F = \sum_{F \subseteq X \subseteq G} (-1)^{e(X)-e(F)} \operatorname{aut}(X) \left( \binom{G}{X} - \binom{H}{X} \right)$$

Kelly’s lemma gives $\binom{G}{X} = \binom{H}{X}$ for all X≠G, every term vanishes except X=G, and as $\binom{G}{G}$ = 1 and $\binom{H}{G}$ = 0, and H ~/= G (no copy of G in H), so the coeff is 1. We get:

$$= (-1)^{e(G)-e(F)} \cdot \operatorname{aut}(G)$$

Theorem 2.27: A graph $G$ is edge reconstructible if there exists a spanning subgraph $F$ of $G$ such that either of the following two conditions holds.

(i) $|G \to H|_F$ takes the same value for all edge reconstructions $H$ of $G$,

(ii) |F \to G| < 2^{e(G)-e(F)-1} \operatorname{aut}(G).

Proof. Let H be an edge reconstruction of G. If condition (i) holds, the left-hand side of (2.8) is zero whereas the right-hand side is nonzero. The inequality of condition (ii) is equivalent, by (2.6), to the inequality

\sum_{F \subseteq X \subseteq G} |G \to G|_X < 2^{e(G)-e(F)-1} \operatorname{aut}(G)

But this implies that |G \to G|_X < \operatorname{aut}(G) for some spanning subgraph X of G such that e(G) - e(X) is even, and identity (the Nash Williams 2.8) is again violated (with F := X). Thus, in both cases, Nash-Williams' Lemma implies that H is isomorphic to G.

Identity (2.8):

$$|G \to G|_F - |G \to H|_F = (-1)^{e(G)-e(F)} \cdot \operatorname{aut}(G)$$

2.6:

$$\sum_{F \subseteq X \subseteq G} |G \to H|_X = |F \to H|$$

Corollary 2.28: A graph G is edge reconstructible if either m > $½ \binom{n}{2}$ or $2^{m-1} \gt$ n!

Proof: 2.27, but set F as the empty graph (edge set empty, n vertices). So, e(F) = 0 and |F → G| = n!. Applying condition ii of 2.27

∣F→G∣ < $2^{e(G)−e(F)−1}$ * aut(G)

This becomes

n! < $2^{m-1}$aut(G)

Since aut(G) $\geq$ 1, this holds whenever $2^{m-1} \gt n!$

If there are more than half the edges of the graph, it is edge constructible is condition 1.

Redo this one:
Redone in class and at least in book: 2.27 with empty results in 2.28.

Theorem 3.5: Euler Tour Characterization (Any proof will do): A connected graph is eulerian if and only if it is even.

The bridges example.

Forward: Eulerian Graph means it enters each vertex once and exits once: so that’s 2 to each vertex. That is even.

Backwards (Even means Eulerian): Connected and even. As the graph is even, cycles exist. Take a cycle. If Cycle C covers all edges, then it is an Eulerian path.

Weird proof, but it’s Veblen’s: even graphs mean a disjoin union of cycles. In this case, we can go from one cycle to another without repeating edges (since the graph is connected).

There’s also the maximal proof one (Will leave that as a thought)

Proposition 3.8: If a graph has a cycle covering in which each edge is covered at most twice, then it has a cycle double cover.

• Let C be a cycle covering of a graph G in which each edge is covered at most twice.

• The sym diff $\triangle\{E(Cc)|Cc\in C$ of the edge sets of the cycles in C is then the set of edges of G which are covered just once by C (sym diff definition)

• By corollary 2.16 (IDR), this set of edges is an even subgraph C’ of G.

  • Corollary 2.16: The symmetric difference of two even subgraphs is an even subgraph.

• By Veblen’s, Cc’ has a cycle decomposition C’

• C $\cup$ C’ is a cycle double cover.

• Each edge lies in exactly two cycles of the cycle set.

Proposition 4.1: In a tree, any two vertices are connected by exactly one path.

• By definition, a tree is a connected graph with no cycles.

• If there are two ways to get to a point, then the 2 points have a path to each other making a cycle

  • If not, then the tree is not connected.

• Formal contradiction:

  • Two distinct paths for uv: P and Q.

  • There is some edge that is in one and not the other (unique).

  • But then P $\cup$ Q contains a cycle

    • Follow P until it diverges from Q, follow Q back to the start point.

Proposition 4.2: Every nontrivial tree has at least two leaves.

• Let P be a longest path in T (Contra)

• The two endpoints of P have to be 1

  • If not, then P is not the longest path

  • If an endpoint (with degree >1) goes back into the path, then there is a cycle and that contradicts a tree.

Theorem 4.3: If T is a tree, then e(T) = v(T) − 1

Book:

If x is a leaf of a tree T, the subgraph T −x is a tree with v(T −x) = v(T)−1 and e(T − x) = e(T) − 1. Because the trivial tree has no edges, we have, by induction on the number of vertices, the following relationship between the numbers of edges and vertices of a tree.

AI:

Induction

Base: v(T) = 1, no edges, so v - 1 = e → 1 - 1 = 0

Step:

• 4.2 says T has at least 2 leaves

  • Either it is maximal path,

  • It isnt,

  • or it goes back into the tree, making it a cycle.

  • So it has to have 2 leaves (endpoints to a path)

• So, T-v is a tree with v(T) - 1 vertices and e(T) - 2 edges.

• By induction, e(T) - 1 = v(T) - 1 -1, so e(T) = v(T) - 1.

Theorem 4.5: Any tournament on 2k vertices contains a copy of each branching on k+1 vertices

• Setup

  • M1: If v1 to v2k is median order of T, so is v1 to v_2k-2 for T - {v_2k-1, v_2k}

    • Proof (necessary?)

      • Any reordering of v1​,…,v2k−2​ that increases forward arcs in the sub-tournament would also increase forward arcs in the full tournament (the arcs to v2k−1 and v2k​ are unaffected). This contradicts maximality of the original ordering.

  • M2: In a median order, each v_i dominates at least half of {v_i+1… v_n}

    • Proof

      • Suppose v_i​ dominates fewer than half of the vertices after it. Then vi​ loses to more than half. Swapping vi​ to the end of the sequence would turn those losses (backward arcs) into forward arcs, netting a gain. This contradicts maximality.

• Induction

  • k = 1, branching on 2 verts = 1 arc.

  • Let v₁ … v_2k be a median order of tournament T

    • Median order is a linear ordering of its vertices that maximizes the number of forward arcs

  • Let B be a branching on k + 1 vertices.

  • Remove a leaf y with parten x to get B’ = B - y on k vertices.

  • Set T’ = T - {v_2k-1, v_2k}.

  • By M1, v₁ … v_2k-2 is a median order of T’, B’ embeds in T’ by induction.

    • B’ covers at least half of vertices v₁ to v_i, 1 <= i <= 2k-2

    • x is predecessor of y in B, and x maps to v_i in T’

  • Count the outneighbors of v_i after position i in the full tournament T:

    • M2 says that v_i dominates at least half from v_i+1 to v_2k, so at least k - i/2 verts

    • at most k - (i+1)/2 vertices of the vertices from v_i+1 to v_2k

  • It follows that there is an outneighbor v_j or v_i in T, where j is between i+1 and 2k and NOT in B;’.

  • Locating y at v_j and adding the vertex y and arc (x,y) to B’, we now have a copy of B in T.

Theorem 4.6: A graph is connected if and only if it has a spanning tree.

• Spanning tree is a tree that covers all points

• Forward: G is connected.

  • No cycles, it is a tree.

  • Otherwise, pick a cycle and remove an edge.

  • Repeat until no cycles remain.

  • Done lol.

• Backwards

  • If G has a spanning Tree, by definition it is connected.

Theorem 4.7: A graph is bipartite if and only if it contains no odd cycle.

Forwards:

• Every edge goes from X to Y.

• Every cycle starts and ends on same point, so you cross an even number of times.

  • Odd cycle cannot exist

Backwards:

• No odd cycle means bipartite

• By theorem 4.6, there is a spanning tree. You can define from a point x:

  • Odd distance as X

  • Even distance as Y

  • Y := V \ X

• Bipartite.

Theorem 4.8: Cayley’s Formula
The number of labelled trees on n vertices is n$^{n-2}$

Count labelled branchings instead (directed trees).

• Count ordered constructions

• Starting with n isolated vertices (n components)

• When there are k components, choose

  • Any of n verts (u)

  • Root of any of the k-1 components that doesn’t contain u (v)

• So at each step, we have n(k-1) choices.

• This means a pi product (idk what its called), so

  • $$\prod_{k=2}^{n}n(k-1)=n^{n-1}*(n-1)!$$

• So we have

  • Labelled Branching (once per edge order)

    • $$\frac{n^{n-1}*(n-1)!}{(n-1)!} = n^{n-1}$$

  • Trees from labelled branching (from n vertices that can be root)

    • $$\frac{n^{n-1}}{n} = n^{n-2}$$

Theorem 4.10: Let T be a spanning tree of a connected graph G, and let S be a subset of its cotree !T. Then C := $\triangle${C_e : e ∈ S} is an even subgraph of G. Moreover, C ∩ !T = S, and C is the only even subgraph of G with this property

The proof is helped with visuals.

• Each fundamental cycle C_e is an even subgraph, it follows from 2.16 (sym diff of two even subgraphs is an even subgraph) that C (the sym diff of the cycles) is also even.

• C $\cap$ !T = S as each edge of S appears in one fundamental cycle

• So, if C’ is any even subgraph of G such that C’ $\cap$ !T = S,

  • (C $\triangle$ C’) $\cap$ T = (C ∩ T) $\triangle$ (C ∩ T) = S $\triangle$ S = ∅

• So C = C’, as even C $\triangle$ C’ = empty.

Corollary 4.11: Let T be a spanning tree of a connected graph G. Every even subgraph of G can be expressed uniquely as a symmetric difference of fundamental cycles with respect to T.

Same as 4.10: C can only be expressed as C := $\triangle${C_e : e ∈ S}; as the sym diff of fundamental cycles with respect to T.

Corollary to 4.10 → 4.12:

Every cotree of a connected graph is contained in a unique even subgraph of the graph.

• Apply 4.10 with S = !T (Cotree)

• C := $\triangle${C_e : e ∈ S} is an even subgraph containing !T, and C $\cap$ !T = !T.

• This also means !T $\subseteq$ C, so !T is contained in an unique even subgraph of the graph.

Theorem 5.1: A connected graph on three or more vertices has no cut vertices if and only if any two distinct vertices are connected by two internally disjoint paths.

Definition:

• Cut Vertex: A vertex that results in a more disconnected graph.

Backward:

• If any two vertices u,w have two internally disjoint paths between them, then deleting any vertex v leaves at least one of those paths intact (at most one passes through v). So G−v is still connected, meaning v is not a cut vertex.

Forward:

• Induction

• Base Case:

  • distance of uv = 1. Then, u and v are adjacent on edge e. Neither u or v are cut vertices, so e is not a cut edge, and lie on a cycle of G

  • Prop 3.2: An edge e of a graph G is a cut edge if and only if e belongs to no cycle of G.

  • u and v are connected by two disjoin paths: edge e, and the rest of C.

    • Meaning two paths with no shared vertices besides u and v

• Induction:

  • Say it holds for distance between uv = k, k $\geq$ 2.

  • Make a new path right before uv, call it uv’ and d(uv’) = k - 1

    • By induction, u and v’ have 2 internally disjoint paths

  • Since v’ is not a cut vertex, G - v’ is connected, so there exists a path for u-v R’. The path meets P’ $\cup$ Q’ (the two disjoint paths for u v’) at u.

  • Let x be the last vertex where R’ meets P’ $\cup$ Q’. Say x lies on P’.

    • Then P = u P’ x R’ v and Q = u Q’ v’ v.

    • These are internally disjoint paths.

Theorem 6.10: Every Jarnik–Prim tree is an optimal tree.

Definition:

• Jarnik Prim tree: Tree is greedy. Keep on adding cheapest edge connecting the current tree to a vertex not yet in the tree.

  • Cheapest meaning the one reachable from the entire tree, not just the root. So the shortest distance from any vertex in the tree.

Proof:

• Base Case: One vertex, no edges. Whatever.

• Induction: Every edge after

  • Let T’ be any optimal tree.

    • If e $\in$ T’, done.

    • If not, T’ + e contains a unique cycle C

  • Let f be the other edge of C incident with r. Then,

    • T’’ := (T’ + e) \ f is a spanning tree

    • w(e) $\leq$ w(f), so

      • w(T’’) = w(T’) + w(e) − w(f) ≤ w(T’)

    • Since T’ is optimal, T’’ must also be an optimal tree.

  • Now consider G’ := G / e (Contracted)

    • Denote r’ by the vertex resulting from the contraction of e.

    • 1-1 correspondence between the set of spanning trees of G that contain e and the set of all spanning trees of G’.

    • Thus, to show T is optimal, we can show T’ = T / e is an optimal tree of G’ (1-1).

  • So, consider T is at some stage of the algorithm. We assume that T is not simply the root vertex r and includes the edge e.

  • T’ := T / e. Then $\partial$ (T) = $\partial$(T’), so edge of min weight in $\partial$(T) is also one in $\partial$ (T’).

  • As the final tree T is JP tree of G, same with T’ and G’.

    • G’ has fewer vertices than G, T’ is optimal, so T is as well.