Question

Let G be a simple planar graph with fewer than 12
vertices.

a) Prove that m <=3n-6; b) Prove that G has a vertex of degree
<=4.

Solution: (a) simple --> bdy >=3. So 3m - 3n + 6 = 3f <= sum(bdy) = 2m --> m - 3n + 6 <=0 --> m <= 3n - 6.

**So for part a, how to get bdy >=3 and 2m? I need a
detailed explanation**

b) Assume all deg >= 5 --> 5n <= sum(deg) = 2m <=
3(3n-6) = 6n - 12 --> 5n <= 6n - 12 or 12 <= n. But n <
12. This contradiction proves that there is a vertex of deg
<=4.

**I need a detailed explanation for part b**

Answer #1

Use proof by induction to prove that every connected planar
graph with less than 12 vertices has a vertex of degree at most
4.

Let
G be a simple graph with at least two vertices. Prove that there
are two distinct vertices x, y of G such that deg(x)= deg(y).

Let G be a simple graph in which all vertices have degree four.
Prove that it is possible to color the edges of G orange or blue so
that each vertex is adjacent to two orange edges and two blue
edges.
Hint: The graph G has a closed Eulerian walk. Walk along it and
color the edges alternately orange and blue.

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.

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.

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.

Let G be an undirected graph with n vertices and m edges. Use a
contradiction argument to prove that if m<n−1, then G is not
connected

Let G be a simple graph with n(G) > 2. Prove that G is
2-connected iff for every set of 3 distinct vertices, a,
b and c, there is an a,c-path
that contains b.

Question 38
A simple connected graph with 7 vertices has 3 vertices of
degree 1, 3 vertices of degree 2 and 1 vertex of degree 3. How many
edges does the graph have?
Question 29
Use two of the following sets for each part below. Let X = {a,
b, c}, Y = {1, 2, 3, 4} and Z = {s, t}. a) Using ordered pairs
define a function that is one-to-one but not onto. b) Using ordered
pairs define...

1) Describe an example of each of the following that may be
found of your kitchen: Explain how your choice falls into this
category, and if there is a chemical name or symbol for it, provide
that as well. Provide a photo of your example with your ID card in
it. a) a compound b) a heterogeneous mixture c) an element (symbol)
Moving to the Caves… Lechuguilla Caves specifically. Check out this
picture of crystals of gypsum left behind in...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 4 minutes ago

asked 20 minutes ago

asked 24 minutes ago

asked 27 minutes ago

asked 37 minutes ago

asked 48 minutes ago

asked 49 minutes ago

asked 49 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago

asked 2 hours ago