Question

Show that if G is connected with n ≥ 2 vertices and n − 1 edges that G contains a vertex of degree 1.

Hint: use the fact that deg(v1) + ... + deg(vn) = 2e

Answer #1

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.

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.

Call a graph on n vertices dendroid if it has n edges and is
connected. Characterize degree sequences of dendroids.

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

Graph Theory.
A simple graph G with 7 vertices and 10 edges has the
following properties: G has six vertices of degree
a and one vertex of degree b. Find a and
b, and draw the graph.
Show all work.

Show that if G is a graph with n ≥ 2 vertices then G has two
vertices with the same degree.

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...

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

please solve it step by step. thanks
Prove that every connected graph with n vertices has at least
n-1 edges. (HINT: use induction on the number of vertices
n)

In lecture, we proved that any tree with n vertices must have n
− 1 edges. Here, you will prove the converse of this statement.
Prove that if G = (V, E) is a connected graph such that |E| =
|V| − 1, then G is a tree.

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 10 minutes ago

asked 18 minutes ago

asked 31 minutes ago

asked 31 minutes ago

asked 42 minutes ago

asked 59 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago