Reference no: EM132363845
SGTA Exercises - Predicate logic, proofs, trees, planar graphs
Q1. Find a counter-example, if possible, to these universally quantified statements (where the domain is integers).
(a) ∀x (x2 ≥ x)
(b) ∀x (x > 0 ∨x < 0)
(c) ∀x (x = 1)
Q2. Prove or disprove that the difference of the squares of two odd numbers is always divisible by 4.
Q3. A forest has 27 vertices and 18 edges. How many connected components does it have? Is it possible for such a graph to have just two leaves?
Q4. Explain why G = (V, E) has no Eulerian walk, where the vertices and edges are given as the sets
V = {a, b, c, d, e, f} and E = {ab, ac, bc, bd, ce, de, df , ef}.
Show that it is possible to add one edge to G to form a simple graph that does have an Eulerian walk by indicating which edge should be added and writing down the Eulerian walk which can be found.
Q5. (a) Which of the bipartite graphs Kn,m have Euler cycles?
(b) Which of the bipartite graphs Kn,m have Euler walks, but not Euler cycles?
Q6. Explain why every edge for which one of its vertices has degree 2 must be included in any Hamiltonian cycle. Hence show that K3,2 does not have a Hamiltonian cycle.
Q7. Give a direct proof that the square of an odd number is odd. (What would be involved in a contrapositive proof?)
Q8. Consider the following steps to solve √(x+3) = 3 - x.
Square both sides: x +3 = x2 - 6x + 9 .
Rearrange: x2 -7x + 6 = 0 .
Factorize: (x -6)(x - 1) = 0 .
Solve: x = 6 or x = 1, since if ab = 0 then a = 0 or b = 0.
Is the argument, and therefore the conclusion, satisfactory?
Q9. Consider the complete graph K5 which is known to be not a planar graph. Remove an edge; now this graph G is planar.
(a) Show how Euler's formula applies to G: V = 5, E = 9 so F = 2 - (V -E) = 6, which number of faces (including the external region) can be seen in the rightmost image above.
(b) Now a simple graph with 6 faces must have at least 6 × 3 'edges on faces'. (Why?)
(c) Since each edge belongs to exactly 2 faces, this means that there would need to be at least (6 × 3) ÷2 = 9 edges. This is correct for the planar graph G, obtained by removing an edge from K5, as all faces are triangular.
(d) Now consider the question of planarity for K itself, which has V = 5 and E = 10; but it is not at all clear how to count faces, or whether the concept is even applicable. Repeat the calculations in (a) - (c) using these values: if K5 is planar then there would need to be 7 faces. (Why?)
(e) Explain why this means that K5 cannot be planar.
Q10. A graph has 9 vertices each of degree 6.
(a) How many edges does it have?
(b) If it was planar, use Euler's formula to calculate the number of faces it would have when drawn on a sphere (or regions if drawn in the plane).
(c) Explain why the graph cannot be planar.
Q11. Consider the graph below.
(a) Does the graph have an Eulerian cycle? Give reasons for your answer. Find one, if it exists.
(b) Does the graph have an Eulerian walk? Give reasons for your answer. Find one, if it exists.
(c) Identify any vertices of degree 2, and hence deduce which edges must be included in every Hamiltonian cycle.
(d) Find a Hamiltonian cycle in the graph.
Q12. Express each of these statements using predicates, quantifiers and logical connectives.
(a) 'A man qualifies for the marathon if he has a recorded time of less than 3 hours, and a woman qualifies for the marathon if she has a recorded time of less than 3.5 hours.'
Define m(x) to be true if x is a man and define P(x, t) to be true if person x has a recorded time less than t, and Q(x) is true if person x qualifies for the marathon.
(b) There is a student who has taken more than 21 credit points in a semester and received all HD grades.
Q13. Prove that for integers n, if n3 +5 is odd then n is even, using a proof by:
(i) contraposition; (ii) contradiction.
Q14. Consider the bipartite graph K3,3 which is known to be not a planar graph. However if one edge is removed, then the resulting graph G is planar.
(a) Show how Euler's formula applies to this graph G, with V = 6 and E = 8.
(b) Note that there are no triangles in a bipartite graph, so the faces of G all have 4 edges (i.e., the faces are quadrilaterals).
(c) Now consider the question of planarity for K3,3 itself, which has V = 6 and E = 9. If planar, how many faces must there be?
(d) With this number of faces, what is the minimum number of edges possible? (Beware, it is a bipartite graph!)
(e) Explain why this means that K3,3 cannot be planar.
Q15. Someone claims to have drawn a map with 11 vertices and 30 edges.
(a) How many faces does the map have if it is drawn on a sphere?
(b) What is the minimum number of edges that a map with this many faces would require?
(c) Is the claim credible?