Graph Theory Exam 2

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, so is F in G-v. 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:
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, leaving

$$= (-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 (2.8) is again violated (with F := X). Thus, in both cases, Nash-Williams' Lemma implies that H is isomorphic to G.

Left side of Nash Williams is constant (same for all H), then it would be zero for all non isomorphic H. But the right side is nonzero. So, every edge reconstruction

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!$

Other condition idk man this shit sucks

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

Redo this one.

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 if 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.

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.

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

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}$

4.10

4.11

4.12

5.1

6.10