a. Prove that having n vertices, where n is a positive integer, is an invariant for graph
isomorphism.
b. Prove that having a vertex of degree 3 is an invariant for graph isomorphism.

Question

Quizplus · Accepted Answer

The Answer is a. Proof:
Suppose

G

and

G^{\prime}

are isomorphic graphs and suppose

G

has

n

vertices, where

n

is a positive integer. By definition of graph isomorphism, there is a one-to-one correspondence

h: V(G) \rightarrow V(G

But

V(G)

is a finite set and two finite sets in one-to-one correspondence have the same number of elements. Therefore, there are as many edges in

V\left(G^{\prime}\right)

as there are in

V(G)

, and so

G

and

G^{\prime}

have the same number of edges.
b. Proof:
Suppose

G

and

G^{\prime}

are isomorphic graphs and suppose

G

has a vertex

v_{0}

of degree 3 . [We must show that

G^{\prime}

has a vertex of degree 3.] By definition of graph isomorphism, there are one-toone correspondences

g: V(G) \rightarrow V\left(G^{\prime}\right)

and

h: E(G) \rightarrow E\left(G^{\prime}\right)

that preserve the edge-endpoint functions in the sense that for all

v

in

V(G)

and

e

in

E(G), v

is an endpoint of

e \Leftrightarrow g(v)

is an endpoint of

h(e)

. Let

e_{1}, e_{2}, \ldots, e_{m}

be the

m

distinct edges that are incident on

v_{0}

, noting that

m=2

or

m=3

because

v_{0}

has degree 3 . Then

h\left(e_{1}\right), h\left(e_{2}\right), \ldots, h\left(e_{m}\right)

are the

m

distinct edges that are incident on

g\left(v_{0}\right)

in

G^{\prime}

. [The reason why

h\left(e_{1}\right), h\left(e_{2}\right), \ldots, h\left(e_{m}\right)

are distinct is that

h

is one-to-one and

e_{1}, e_{2}, \ldots, e_{m}

are distinct. And the reason why

h\left(e_{1}\right), h\left(e_{2}\right), \ldots, h\left(e_{m}\right)

are incident on

g\left(v_{0}\right)

is that

g

and

h

preserve the edge-endpoint functions of

G

and

G^{\prime}

and

e_{1}, e_{2}, \ldots, e_{m}

are incident on

v_{0} . J

Also, there are no edges incident on

g\left(v_{0}\right)

other than the ones that are images under

g

of edges incident on

v

because

g

is onto and

g

and h preserve the edge-endpoint functions of

G

and

\left.G^{\prime}\right]

. Thus the number of edges incident on

v_{0}

equals the number of edges incident on

g\left(v_{0}\right)

. Finally, an edge

e

is a loop at

v_{0}

if, and only if,

h(e)

is a loop at

g\left(v_{0}\right)

, so the number of loops incident on

v_{0}

equals the number of loops incident on

g\left(v_{0}\right)

. [For since

g

and

h

preserve the edge-endpoint functions of

G

and

G^{\prime}, v_{0}

is an endpoint of

e

in

G

if, and only if,

g\left(v_{0}\right)

is an endpoint of

h(e)

in

G^{\prime}

. It follows that

v_{0}

is the only endpoint of e in

G

if, and only if,

g\left(v_{0}\right)

is the only endpoint of

h(e)

in

G^{\prime}

.] Now the degree of

v_{0}

, which is 3 , equals the number of edges incident on

v_{0}

plus the number of edges incident on

v_{0}

that are loops (since a loop contributes 2 to the degree of

\left.v_{0}\right)

. But we have already shown that the number of edges incident on

v_{0}

equals the number of edges incident on

g\left(v_{0}\right)

and that the number of loops incident on

v_{0}

equals the number of loops incident on

g\left(v_{0}\right)

. Hence

g\left(v_{0}\right)

also has degree 3 . Note: An alternative proof for this problem could consider two cases separately. In one case the vertex v0 in G of degree 3 would have three distinct edges incident on it, and in the other case there would be one edge and one loop incident on it.

A Prove That Having N Vertices, Where N Is a Positive