u/TopDownView

To solve: Find all minimum spanning trees for graph G that can be obtained using (a) Kruskal's algorithm and (b) Prims's algorithm starting with vertex t.

Graph G:

https://preview.redd.it/zr7gj8dkjx0h1.png?width=182&format=png&auto=webp&s=eb27b72760b47fe835bccb10b87d241281dd5f87

Incomplete solution:

https://preview.redd.it/aoi0li2ljx0h1.png?width=793&format=png&auto=webp&s=5a5a53f747386f71ad46595fcfae0d8c8ceac20e

Isn't it that there are 4 orders when using Kruskal's since we have two choices of 2's and two choices of 5's (2 x 2 = 4 ways to order edges)?

Isn't it that there are 2 orders when using Prim's since we have two choices of 2's (starting from vertex t: t -> w -> x -> u -> either v or y -> z)?

Graph G:

https://preview.redd.it/od96g0s9bq0h1.png?width=126&format=png&auto=webp&s=08e85c1940cbb6209dc53cbda59650e1752120d7

Wrong solution:

https://preview.redd.it/t8i1kylabq0h1.png?width=342&format=png&auto=webp&s=1ed522b66a9f080b0ff20cd2e5e01e2efc4243a0

Correct solution:

https://preview.redd.it/w2mityhbbq0h1.png?width=1116&format=png&auto=webp&s=5e13bfda93a57f68a7d413c72db65ddacbf162d0

The graph in the first row of the wrong solution in not a tree. Also, wrong solution misses two spanning trees: the one in the first row, second column of the correct solution, and the one in the second row, first column (of the correct solution, both are purple).

Is this observation correct?

Dijkstra's Algorithm:

https://preview.redd.it/uo9weib8fn0h1.png?width=615&format=png&auto=webp&s=080d59dcd8148cfce986fa08616e27e855bc715b

https://preview.redd.it/vx824t7afn0h1.png?width=614&format=png&auto=webp&s=ffa594a70dda5595dec2110a52d59001b7f5d6b0

Proof of correctness of Dijkstra's Algorithm:

https://preview.redd.it/16gvshlffn0h1.png?width=612&format=png&auto=webp&s=660ff5e6e517d47008da2efb5ca1f73ee6386124

https://preview.redd.it/mv4s26vgfn0h1.png?width=612&format=png&auto=webp&s=de73178038ae685dbb8ef4c81a7b4d9f339367b9

https://preview.redd.it/2laqd55ifn0h1.png?width=612&format=png&auto=webp&s=aa1245fbef8e5f01313b3a3285556af10fb06fd5

Specifically, I don't understand the second part of the proof, the part after the illustration.

I'll start with this question: Why is LSP(a,v) >= LSP(a,s) + w(s,t)? Also, what is 'r' in '...then t would be added to T instead of r'?

This is what I could come up with (but it seems to me it's unrelated to the proof above):

https://preview.redd.it/lp7bfz6kfn0h1.png?width=1212&format=png&auto=webp&s=faa24f45229f1fbde31f6d0e379ca1bf3053a5a1

https://preview.redd.it/jzv4fhghgrzg1.png?width=612&format=png&auto=webp&s=8cfa14a850e81f203fa7909ee2a96e35706daedf

https://preview.redd.it/yajtu73igrzg1.png?width=611&format=png&auto=webp&s=0750eeb635a9fe721f764cfd0c72a5f5555d82d1

Isn't the illustration missing one more blue edge, so that both, T_1 (black) and T (blue) have the same number of edges (7)?

https://preview.redd.it/cxdv3lrrgrzg1.png?width=506&format=png&auto=webp&s=195a7286951be6af11918cba8f16ed8141cdf685

Why isn't cut fill pattern of earth mesh showed in floor plan?

It looks like the floor plan isn't cutting the earth mesh, only showing its projection.

https://preview.redd.it/0pagkk5ruizg1.png?width=806&format=png&auto=webp&s=1cc2e3cb6b78f49e8a745f4311ff0e7642b20ae6

The textbook I'm using claims:

1. The height of a rooted tree is a maximum level of any vertex of the tree.
2. A full binary tree is a binary tree in which each parent has exactly two children.
3. A full binary tree of height h has 2^h leaves.

If 1., 2., and 3. are true, then this is a full binary tree of height 4 that has 2^4 = 16 leaves:

https://preview.redd.it/jgidvpvx9dzg1.png?width=1122&format=png&auto=webp&s=df70e75c4e939a77129804ff04155037ccd5bea2

Clearly, this tree hasn't got 16 leaves.

Am I missing something? Are these 3 claims true?

Find all nonisomorphic trees with 5 vertices

Isn't the solution below wrong?

https://preview.redd.it/0tw6twweb6zg1.png?width=344&format=png&auto=webp&s=6d7daddc4c6b6b0dbd8d0945fb798782835e51ff

Top 3 trees are isomorphic.

My solution (the numbers are vertex degrees):

https://preview.redd.it/dt4x2rejb6zg1.png?width=1258&format=png&auto=webp&s=9936a6fbbcc8e63088c6347d9b6b0d967fe4c1fb

So there are 3 nonisomorphic trees with 5 vertices. My blue tree is isomorphic to top 3 trees of the wrong solution. My red tree is the same as the bottom tree in the wrong solution.

Exercise:

Prove that every nontrivial tree has at least two vertices of degree 1 by filling in the details and completing the following argument: Let T be a nontrivial tree and let S be the set of all paths from one vertex to another in T. Among all the paths in S, choose a path P with a maximum number of edges. (Why is it possible to find such a P?) What can you say about the initial and final vertices of P? Why?

I'm only interested in the question in the parenthesis: Why is it possible to find such a P?

Is the following answer correct? If not, why?

Answer (proof):

1. FTSOC, assume it is not possible to find such P among all paths
2. That means there are multiple paths between two vertices that have the same number of edges
3. That implies a tree has at least one circuit
4. But that contradicts the definition of tree
5. Therefore, it is possible to find a path P with maximum number of edges

QED

Considering my previous post...

Proof:

1. Suppose G is a circuit-free graph with n vertices and >=n-1 edges
2. Assume for contradiction that G is not connected
3. Then, G consists of k connected components (where k>=2)
4. Since G is circuit-free, each of G_1,G_2,...,G_k connected components is also circuit-free
5. So each G_1,G_2,...,G_k is circuit-free and connected
6. Thus, each G_1,G_2,...,G_k is a tree where G_1 has n_1 vertices and n_1-1 edges, G_2 has n_2 vertices and n_2-1 edges,..., G_k has n_k vertices and n_k-1 edges
7. So, the number of edges of G equals |E(G_1)|+|E(G_2)|+...+|E(G_k)| = (n_1-1)+(n_2-1)+...+(n_k-1)=n_1+n_2+...+n_k -1-1-...-1 = n-k (because n_1+n_2+...+n_k = n and -1-1-...-1 = (-1)*k = -k)
8. So, G has n-k edges
9. But this contradicts our supposition that G has >=n-1 edges since n-k<n-1 (because k>=2)
10. Therefore, G is connected

QED

Is this proof finished as is? Or do we also have to mention (by Corollary 10.4.5*) that if G has >n-1 edges, then it must have a circuit?

The way I see it, we have proved the following statement:

If a graph G is circuit-free, has n vertices and >=n-1 edges, then G is connected.

So, it is true that G is connected given that it has n-1 or &gt;n-1 edges.**

This is what is asked of us, isn't it? Or, do we actually have to prove the following 2 statements, a) and b)?

a) If a graph G is circuit-free, has n vertices and n-1 edges, then G is connected.
b) If a graph G is circuit-free, has n vertices and >n-1 edges, then G is connected.

*Corollary 10.4.5: If G is any graph with n vertices and m edges, where m and n are positive integers and m>=n, then G has a circuit.

**Here, I'm implying truth table values for OR.

1. Suppose G is any circuit-free, connected graph with 10 vertices and 9 edges.
2. By definition, for any positive integer n, if G is a connected graph with n vertices and n-1 edges, then G is a tree.
3. By 1. and 2., G is a tree.
4. By definition, a graph is called a tree <-> it is circuit-free and connected.
5. By 1. and 4., G is a tree.
6. 1., 2., and 4. confirm our supposition was true.
7. Therefore, G is connected.

QED

Is this proof correct? I seems to me this proof is neither direct proof, nor proof by contradiction? Can we make a 'true' supposition without reaching a contradiction? And then use definitions as building blocks to reach the conclusion: 'supposition/statement is true'?

Suppose that v is a vertex of degree 1 in a connected graph G and that e is the edge
incident on v. Let G′ be the subgraph of G obtained by removing v and e from G. Must
G′ be connected? Why?

Solution:

1. Let the set of vertices of G be V(G) = {v, v_1,..., v_n} where v is adjacent to v_1 via the edge e
2. Let the set of vertices of G' be V(G') = {v_1,...., v_n}
3. By definition, subgraph G' preservers edge-endpoint connections of G
4. So, if vertices V(G) of G are connected, then vertices V(G') of G' are connected
5. Therefore G' is connected

QED

Is my solution correct?

Prove: If graph G has a Hamiltonian circuit and G is isomorphic to G', then G' has a Hamiltonian circuit

*Assume this statement is true: If graph G has a simple circuit of length k and G is isomorphic to G', then G' has a simple circuit of length k

1. Suppose G and G' are isomorphic graphs and G has a Hamiltonian circuit H
2. By def., H is a simple circuit that includes every vertex of G
3. Let H be of length k
4. Then, by assumption, G' has a simple circuit H' of length k that includes every vertex of G'
5. Therefore, G' has a Hamiltonian circuit

QED

Is my proof correct?

Edit:

*This statement is proved in one of the previous exercises.

Prove: If G is a graph that has an Euler circuit and G and G' are isomorphic, then G' has an Euler circuit.

1. Suppose G and G' are isomorphic graphs and G has an Euler circuit (G is connected and every vertex of G has positive even degree)
2. Suppose w and x are any two vertices in G'
3. Because g:V(G)->V(G') is a bijection, there exist vertices u,v in G s.t. g(u)=w and g(v)=x
4. Since G is connected, there exists a walk from u to v
5. Then since h:E(G)->E(G') is a bijection, and since g and h preserve edge-endpoint functions, there exist a walk from g(u)=w to g(v)=x in G'
6. Also, because of the same characteristics of g and h, g(u)=w and g(v)=x have positive even degree
7. Therefore G' has an Euler circuit

QED

Is my proof correct?