Complex profile line weights are all over the place - How do I fix this?
Line weight of wall core should be thick, while the finish should be thin.
Suppose G is a connected graph and T is a circuit-free subgraph of G. Suppose also that if any edge e of G not in T is added to T, the resulting graph contains a circuit. Prove that T is a spanning tree for G.
Proof idea: Proof aims to show that T satisfies the definition of a spanning tree. -> 'A spanning tree for a graph G is a subgraph of G that contains every vertex of G and is a tree.'
Proof:
QED
---
Is my proof correct?
Prove that if G is a graph with spanning tree T and e is an edge of G that is not in T, then the graph obtained by adding e to T contains one and only one set of edges that forms a circuit.
Fact from the previous exercise: Given any two distinct vertices of a tree, there exists a unique path from one to the other.
Proof:
QED
---
Is my proof correct?
This is the solution from the textbook (using direct proof method):
Prove: Given any two distinct vertices of a tree, there exists a unique path from one to the other.
Proof:
QED
Illustration of 4 cases:
---
Is my proof correct?
I understand the proof could be more concise. This is the solution from the textbook:
IMO, the main distinction between my proof and textbook solution is that my proof doesn't use constriction assume 'no parallel edges in T'. So circuits in my proof could be formed with or without parallel edges. But maybe because of this, my proof is longer?
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:
Incomplete solution:
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:
Wrong solution:
Correct solution:
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:
Proof of correctness of Dijkstra's Algorithm:
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):
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)?
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.
The textbook I'm using claims:
If 1., 2., and 3. are true, then this is a full binary tree of height 4 that has 2^4 = 16 leaves:
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?
Top 3 trees are isomorphic.
My solution (the numbers are vertex degrees):
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):
QED
Considering my previous post...
Proof:
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 >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.
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:
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
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.
QED
Is my proof correct?
