Question

30. a) Show if G is a connected planar simple graph with v vertices and e edges with v ≥ 3 then e ≤ 3v−6.

b) Further show if G has no circuits of length 3 then e ≤ 2v−4.

Answer #1

**PLEASE LIKE IT RAISE YOUR THUMBS UP**

**IF YOU ARE HAVING ANY DOUBT FEEL FREE TO ASK IN COMMENT
SECTION**

show that any simple, connected graph with 31 edges and 12 vertices
is not planar.

A graph is called planar if it can be
drawn in the plane without any edges crossing. The Euler’s formula
states that v − e + r = 2,
where v,e, and r are the numbers of vertices,
edges, and regions in a planar graph, respectively. For the
following problems, let G be a planar simple graph with 8
vertices.
Find the maximum number of edges in G.
Find the maximum number of edges in G, if G
has no...

Let G = (V,E) be a graph with n vertices and e edges. Show that
the following statements are equivalent:
1. G is a tree
2. G is connected and n = e + 1
3. G has no cycles and n = e + 1
4. If u and v are vertices in G, then there exists a unique path
connecting u and v.

Suppose we are going to color the vertices of a connected planar
simple graph such that no two adjacent vertices are with the same
color.
(a) Prove that if G is a connected planar simple graph, then G
has a vertex of degree at most five.
(b) Prove that every connected planar simple graph can be
colored using six or fewer colors.

A spanning tree of connected graph G = (V, E) is an acyclic
connected subgraph (V, E0 ) with the same vertices as G. Show that
every connected graph G = (V, E) contains a spanning tree. (It is
the connected subgraph (V, E0 ) with the smallest number of
edges.)

Let G be a connected planar graph with 3 or more vertices which
is drawn in the plane. Let ν, ε, and f be as usual. a) Use P i fi =
2ε to show that f ≤ 2ε 3 . b) Prove that ε ≤ 3ν − 6. c) Use b) to
show that K5 is not planar.

If a connected 3-regular planar graph G has 18
vertices, then the number of faces of a planar representation of
G is..........

Let there be planar graph G with 12 vertices where every
vertices may or may not be connected by an edge. The edges in G
cannot intersect. What is the maximum number of edges in G. Draw an
example of G. What do you notice about the faces and the maximum
number of edges?

Let G be a connected simple graph with n vertices and m edges.
Prove that G contains at least m−n+ 1 different subgraphs
which are polygons (=circuits). Note: Different polygons
can have edges in common. For instance, a square with a diagonal
edge has three different polygons (the square and two different
triangles) even though every pair of polygons have at least one
edge in common.

Suppose that a connected planar graph has eight vertices each of
degree 3 then how many regions does it have?And suppose that a
polyhedron has 12 triangular faces then determine the number of
edges and vertices.

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 5 minutes ago

asked 10 minutes ago

asked 10 minutes ago

asked 33 minutes ago

asked 43 minutes ago

asked 43 minutes ago

asked 57 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago