Question

I.15: If G is a simple graph with at least two vertices, prove that G has two vertices of the same degree.

Hint: Let G have n vertices. What are possible different degree values? Different values if G is connected?

Answer #1

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

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.

Suppose G is a simple, nonconnected graph with n vertices that
is maximal with respect to these properties. That is, if you tried
to make a larger graph in which G is a subgraph, this larger graph
will lose at least one of the properties (a) simple, (b)
nonconnected, or (c) has n vertices.
What does being maximal with respect to these properties imply
about G?G? That is, what further properties must GG possess because
of this assumption?
In this...

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.

Prove that every graph has two vertices with the same degree.
(hint: what are the possible degrees?)

Prove that if G is a connected graph with exactly 4 vertices of
odd degree, there exist two trails in G such that each edge is in
exactly one trail. Find a graph with 4 vertices of odd degree
that’s not connected for which this isn’t true.

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.

(a) Let L be a minimum edge-cut in a connected graph G with at
least two vertices. Prove that G − L has exactly two
components.
(b) Let G an eulerian graph. Prove that λ(G) is even.

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

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 13 minutes ago

asked 13 minutes ago

asked 17 minutes ago

asked 19 minutes ago

asked 22 minutes ago

asked 25 minutes ago

asked 30 minutes ago

asked 33 minutes ago

asked 47 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago