Introduction to Graph Theory · Problem 2.14

Simple graphs — Darij Grinberg

Mathematics — Graph Theory · connected-graph-degree-sequence-identification

Problem

Let

n \geq 2

be an integer. Let

G

be a connected simple graph with

n

vertices. (a) Describe

G

if the degrees of the vertices of

G

are

1, 1, 2, 2, \ldots, 2

(exactly two

1

's and

n-2

many

2

's). (b) Describe

G

if the degrees of the vertices of

G

are

1, 1, \ldots, 1, n-1

. (c) Describe

G

if the degrees of the vertices of

G

are

2, 2, \ldots, 2

. Here, to ``describe''

G

means to explicitly determine (with proof) a graph that is isomorphic to

G