Define planar graph. Prove that for any connected planar graph, v - e + r = 2 Where v, e, r is the number of vertices, edges, and regions of the graph respectively. Prove that 5^2n... Define planar graph. Prove that for any connected planar graph, v - e + r = 2 Where v, e, r is the number of vertices, edges, and regions of the graph respectively. Prove that 5^2n - 1 is divisible by 24. Draw the Hasse diagram representing the positive divisors of 36 and 45. Show that the relation R defined by (a, b) R (c, d) iff a + b = c + d is an equivalence relation. Explain various Rules of Inference for Propositional Logic. Show that every Cyclic group is Abelian. Prove that a lattice with 5 elements is not a Boolean algebra. Define Pigeon hole Principle. Write the contra positive of the implication: 'if it is Sunday then it is a holiday.' Prove that G = {0, 1, 2, 3, 4, 5, 6} is an abelian group of order 7 with respect to addition modulo 7. Prove or disprove that the intersection of two normal subgroups of a group G is again a normal subgroup of G. Define subgroup, normal subgroup, Quotient group, with an example for each. Read more

Steps to Solve

1. Define Planar Graph A planar graph is a graph that can be drawn on a plane without any edges crossing each other.

2. State Euler's Formula For any connected planar graph, Euler's formula states: $$ V - E + R = 2 $$ where ( V ) is the number of vertices, ( E ) is the number of edges, and ( R ) is the number of regions formed by the graph.

3. Prove Euler's Formula To prove this formula, we can use mathematical induction or perform a direct proof.

   • Base Case: For a simple graph with one vertex and no edges, ( V = 1 ), ( E = 0 ), ( R = 1 ) (the one region is the entire plane). Thus: $$ 1 - 0 + 1 = 2 $$

   • Inductive Step: Assume it's true for ( k ) edges. Adding a new edge can either increase ( E ) and ( R ) by one or connect two vertices already in the previous configuration without changing ( R ).

4. Define Equivalence Relation An equivalence relation on a set is a relation that is reflexive, symmetric, and transitive.

5. Prove the Relation ( R ) is Equivalence For the relation ( R ) defined as "a is congruent to b modulo m," prove:

   • Reflexive: For any integer ( a ), ( a \equiv a \mod m ) (true because the remainder when ( a ) is divided by ( m ) is ( 0 )).
   • Symmetric: If ( a \equiv b \mod m ), then ( b \equiv a \mod m ) (true as equality is symmetric).
   • Transitive: If ( a \equiv b \mod m ) and ( b \equiv c \mod m ), then ( a \equiv c \mod m ) (true by properties of congruence).

6. Define ( 5^{2n} - 1 ) for Divisibility To prove ( 5^{2n} - 1 ) is divisible by ( 24 ):

• Note that ( 5^{2n} - 1 = (5^n - 1)(5^n + 1) ).

7. Divisibility by 3 Both ( 5^n - 1 ) and ( 5^n + 1 ) are consecutive integers; at least one is divisible by ( 3 ).

8. Divisibility by 8 For ( n \geq 1 ), observe ( 5^2 \equiv 1 \mod 8 ) implies ( 5^{2n} \equiv 1 \mod 8 ). Thus ( 5^{2n} - 1 \equiv 0 \mod 8 ).

9. Combine Results Since ( 5^{2n} - 1 ) is divisible by both ( 8 ) and ( 3 ): $$ \text{lcm}(8, 3) = 24 $$

10. Draw Hasse Diagram For the numbers ( 36 ) and ( 45 ) identify and represent their positive divisors using a Hasse diagram.

11. Show Rules of Inference Explain Modus Ponens, Modus Tollens, and others related to propositional logic.