Question

In: Advanced Math

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 graph of order ≥3 is bounded by a triangle.

Expert Solution

(a)

If an edge e of a maximal planar graph is in exactly two triangles then G/e is also maximal planar. (Since G/e has exactly three fewer edges.)

If G is a maximal planar graph with n≥4 vertices then there are at least n such edges. (Induction on n.)

Let G be a maximal planar graph with at least four vertices. Assume that there are vertices u,v such that G−{u,v} is disconnected. Let X be one component of G−{u,v} and let Y be another.

Contract edges of G until we're left with just u and v along with one vertex of X and one vertex of Y.

Since there are now only four vertices, we must be left with K4. But then removing u and v can't disconnect the graph, so we have a contradiction.

Hence a maximal planar graph is connected always.

c)

Observe that it isn't true for n=1 and n=2 so let n≥3.

Assume to the contrary that there is a maximal planar graph G=(V,E) embedded in the plane with a face that is not a triangle.

Clearly the graph is connected, for otherwise we could add any edge between the outer-boundary of any two components. Furthermore, the boundary of each region is a cycle. To see this, first consider the case where the boundary is acyclic. then it is a tree with at least three vertices. Adding any edge to a tree on three or more vertices preserves planarity, so it couldn't be maximal. now assume that the boundary contains a cycle but is not solely a cycle. Then we have a cycle with trees branching off the cycle. since a tree contains at least two leaves, there is one leaf of the tree that is not in the cycle. An edge can be added from this leaf to any vertex in the cycle that is not also in the tree in question, contradicting maximality. Thus the boundary of each face must be a cycle.

Then the face that is not a triangle must have three consecutive vertices on its boundary, say and where but . then we may safely add the edge , contradicting maximality. Thus, every face of a maximal planar graph on n≥3 vertices is a triangle.

I am not very sure in part b). So I am unable to answer this part.

Ask if any quarries. Thank you

Colby Messinger answered 2 years ago

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.

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)

Determine all maximal planar graphs G of order 3 or more such that the number of...

Determine all maximal planar graphs G of order 3 or more such that the number of regions in a planar embedding of G equals its order.

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

A maximal plane graph is a plane graph G = (V, E) with n ≥ 3...

A maximal plane graph is a plane graph G = (V, E) with n ≥ 3 vertices such that if we join any two non-adjacent vertices in G, we obtain a non-plane graph. a) Draw a maximal plane graphs on six vertices. b) Show that a maximal plane graph on n points has 3n − 6 edges and 2n − 4 faces. c) A triangulation of an n-gon is a plane graph whose infinite face boundary is a convex n-gon...

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.

If G = (V, E) is a graph and x ∈ V , let G \...

If G = (V, E) is a graph and x ∈ V , let G \ x be the graph whose vertex set is V \ {x} and whose edges are those edges of G that don’t contain x. Show that every connected finite graph G = (V, E) with at least two vertices has at least two vertices x1, x2 ∈ V such that G \ xi is connected.

Give an example of two non-isomorphic maximal planar graphs of the same order.

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

1) a) Let k ≥ 2 and let G be a k-regular bipartite graph. Prove that G...

1) a) Let k ≥ 2 and let G be a k-regular bipartite graph. Prove that G has no cut-edge. (Hint: Use the bipartite version of handshaking.) b) Construct a simple, connected, nonbipartite 3-regular graph with a cut-edge. (This shows that the condition “bipartite” really is necessary in (a).) 2) Let F_n be a fan graph and Let a_n = τ(F_n) where τ(F_n) is the number of spanning trees in F_n. Use deletion/contraction to prove that a_n = 3a_n-1 - a_n-2...