Let G be a simple planar graph with no triangles. (a) Show that G has a...

Let G be a simple planar graph with no triangles.

(a) Show that G has a vertex of degree at most 3. (The proof was sketched in the lectures, but you must write all the details, and you may not just quote the result.)

(b) Use this to prove, by induction on the number of vertices, that G is 4-colourable.

Expert Solution

Colby Messinger answered 2 years ago

Let G be a simple graph. G is said to be maximal planar if it is...

Let G be a simple graph. G is said to be maximal planar if it is planar and the addition of any new edge to G results in a (simple) non-planar graph. Examples of maximal non-planar graphs are K4 , K5 minus an edge, and K3,3 minus an edge. (a) Show that a maximal planar graph is connected. (b) Show that a maximal planar graph of order ≥3 has no bridges. (c) Show that every face of a maximal planar...

let G be a simple graph. show that the relation R on the set of vertices...

let G be a simple graph. show that the relation R on the set of vertices of G such that URV if and only if there is an edge associated with (u,v) is a symmetric irreflexive relation on G

Let G be a simple graph. Prove that the connection relation in G is an equivalence...

Let G be a simple graph. Prove that the connection relation in G is an equivalence relation on V (G)

13.6 Let G be a simple connected cubic plane graph, and let pk be the number...

13.6 Let G be a simple connected cubic plane graph, and let pk be the number of k-sided faces. By counting the number of vertices and edges of G, prove that 3p3 + 2p4 + p5 - c7 - 2p8 - • • • = 12. Deduce that G has at least one face bounded by at most five edges.

Let n ≥ 3. Show that if G is a graph with the same chromatic polynomial...

Let n ≥ 3. Show that if G is a graph with the same chromatic polynomial as Cn, then G is isomorphic to Cn. (Hint: Use induction. What kind of graph must G − e be for any edge e? Why?)

Let G be a graph. prove G has a Eulerian trail if and only if G...

Let G be a graph. prove G has a Eulerian trail if and only if G has at most one non-trivial component and at most 2 vertices have odd degree

Let G be a simple undirected graph with n vertices where n is an even number....

Let G be a simple undirected graph with n vertices where n is an even number. Prove that G contains a triangle if it has at least (n^2 / 4) + 1 edges using mathematical induction.

Let G be a connected graph and let e be a cut edge in G. Let...

Let G be a connected graph and let e be a cut edge in G. Let K be the subgraph of G defined by: V(K) = V(G) and E(K) = E(G) - {e} Prove that K has exactly two connected components. First prove that e cannot be a loop. Thus the endpoint set of e is of the form {v,w}, where v ≠ w. If ṽ∈V(K), prove that either there is a path in K from v to ṽ, or...

Let A be incidence matrix of graph G. prove if G has a cycle, then null...

Let A be incidence matrix of graph G. prove if G has a cycle, then null space of transpose of A is not {0} (there exists non-trivial solution of (A^T)y=0)

prove by induction that for any simple connected graph G, if G has exactly one cycle...

prove by induction that for any simple connected graph G, if G has exactly one cycle then G has the same number of edges and nodes

Question