Introduction to Graph Theory · Problem 2.8

Simple graphs — Darij Grinberg

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

Problem

Let

n \geq 2

be an integer. Let

G

be a simple graph with

n

vertices. (a) Describe

G

if the degrees of the vertices of

G

are

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

. (b) Let

a

and

b

be two positive integers such that

a + b = n

. Describe

G

if the degrees of the vertices of

G

are

1, 1, \ldots, 1, a, b

. Here, to ``describe''

G

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

G