Graph Coloring Problem

Please use words to describe the solution process: Let G be a graph with n vertices that is not a complete graph. Prove that x (G) < n HINT: If G does not contain k3 as a subgraph, then every face must have degree at least 4. *(Please see attachment for proper symbols)

Graph Coloring Problem

Please use words to describe the solution process: Let G be a graph with exactly one cycle. Prove that x(G) is less than or equal t0 3. *(Please see attachment for proper symbols)

Propositional Logic : DeMorgan's Laws and Truth Tables

Please see the attached file for the fully formatted problems. Verify DeMorgan's laws (equation 1 and 2 below) using truth tables. Prove the generalized DeMorgan’s laws: (1) (NOT(p1 p2 .... pk)) (2) (NOT(p1+p2+...+pk)) by induction on k, using the basic laws: NOT(pq) NOT(p+q) Then, justify the ge ...continues

Propositional Logic : Commutitivity of Sums and Products

Please see the attached file for the fully formatted problems. Prove that: p1+p2+...+pn is equivalent to the sum (logical OR) of the pi’s in any order. and p1p2 ... pn is equivalent to the product (logical AND) of the pi’s in any order.

Discrete Structures : Coloring

Let G be a properly colored graph and let us suppose that one of the colours used is red. The set of all red-coloured vertices have a special property. What is it? Graph colouring can be thought of as partitioning V(G) into subsets with this special property. (See attachment for full background)

Discrete Math : Proof that there must be 12 Pentagons on a Soccer Ball

A soccer ball is formed by stitching together pieces of material that are regular pentagons and regular hexagons. Each corner of a polygon is the meeting place for exactly three polygons. Prove that there must be exactly 12 pentagons. (Please see attachment for full question and background)

Discrete Mathematics : Prove that a 5-regular graph with 10 vertices is nonplanar.

Let G be a 5-regular graph with ten vertices. Prove that G is nonplanar.

Find values of p for which the faces of a planar p-regular graph are all triangles.

The faces of a planar p-regular graph are all triangles (that is each face has degree three). Determine, with proof, the values of p for which this is possible. (Remember a p-regular graph has all vertices of degree p).

Discrete Structures - Define and Prove

Use words to describe the solution process. No programming. 1. (a) Define a tree. (b) Define a bipartite. (c) Prove the following: Every tree is a bipartite.

Chromatic Number; Planar

Use words to describe the solution process. No programming. 2. Let G = (V,E) be a graph where V {1,2,3,4,5,6,7,8,9,10,11,12} and E contains all edges connecting to vertices a and b such that ab=0 (mod 3). What is the chromatic number of G? Is G planar?