MAT344H1.doc

Page 1 of 32

Graphs and Subgraphs

Definition: Graph

A graph G is a triple

(

)

(

)

(

)

G

GEGV

ψ

,, where

1)

(

)

GV is a finite set. The elements of

(

)

GV are called the vertices of G.

2)

(

)

GE is a finite set. The elements of

(

)

GE are called the edges.

3) G

ψ

is a function which associates to every edge of an unordered pair of not necessarily distinct vertices. G

ψ

is called the incidence function.

Example

Let

(

)

{

}

4321 ,,, vvvvGV=.

Let

(

)

{

}

87654321 ,,,,,,, eeeeeeeeGE=.

Let

(

)

111 vve

G=

ψ

,

(

)

232 vve

G=

ψ

,

(

)

223 vve

G=

ψ

,

(

)

314 vve

G=

ψ

,

(

)

325 vve

G=

ψ

,

(

)

146 vve

G=

ψ

,

(

)

427 vve

G=

ψ

,

(

)

438 vve

G=

ψ

.

The graph looks like:

Could have drawn it like this:

Definition: Planar

If a graph G can be drawn such that edges only intersect at their ends, then G is called planar.

Example

Consider

3,3

k. Prove that it’s not planar.

v1

v4

v2 v3

e1 e2

e3 e4 e5

e6 e7

e8

v5

v6

3,3

k

e9

v1

v4

v2

v3

v1

v4

v2 e1

e2

e3

e4

e5

e6

e7

e8

www.notesolution.com

MAT344H1.doc

Page 2 of 32

Cycle-Chord technique. Observe that

3,3

k contains a cycle which covers every vertex:

1258396624411

vevevevevevev .

There is nowhere to place

9

e!

Vocabulary

1) If

(

)

uve =

ψ

, then u and v are the ends of e.

2) e is said to join u and v.

3) u and v are said to be incident to the edge.

4) u and v are said to be adjacent.

5) If

v

u

=

, then e is said to be a loop.

6) If

v

u

≠

, then e is said to be a link.

Definition: Simple

A graph is said to be simple if it has no loops and no two edges join the same pair of vertices.

VERTEX DEGREES

Definition: Vertex Degrees

The degree of a vertex v of a graph G, denoted

(

)

vdG, is defined to be the number of edges that end at the

vertex (loops count twice).

Example

Fact

(

)

( )

∈

=

GVv

Gvd

ε

2, where

ε

is the number of edges.

Proof:

• To begin, cut each edge into two pieces. Count the resulting half-edges in two different ways.

3

3

3 5

v1

v4

v2

v3

e1

e2

e3

e4

e5

e6

e7

e8

v5

v6

www.notesolution.com

MAT344H1.doc

Page 3 of 32

• Count 1: Label every half edge by the vertex it ends at. The number of edges labeled with some vertex v is

clearly

(

)

vdG. So the number of half-edges is

(

)

( )

∈GVv

Gvd.

• Count 2: There are clearly twice as many half-edges as edges.

Fact

In a graph, the number of vertices with odd degree is even.

Proof:

• Let

(

)

(

)

GVGV≤even be the set of vertices of G with even degrees. Similarly define

(

)

(

)

GVGV≤odd .

•

(

)

( )

(

)

( )

(

)

( )

∈∈∈

+==

oddeven

2

GVv

G

GVv

G

GVv

Gvdvdvd

ε

, so

(

)

( )

∈oddGVv

Gvd must be even, so the number of vertices

with odd degree must be even.

Problem

1) In a group of 8 persons, is it possible that everyone knows exactly 3 others? Yes.

2) In a group of 7 persons, is it possible that everyone knows exactly 3 others? No.

APPLICATION: THE MOUNTAIN CLIMBERS PUZZLE

Consider 2 mountaineers approaching a mountain range from opposite sides. Is it possible for the climbers to

always be at the same height and reach the summit?

Theorem

Two mountaineers can indeed clime in the required fashion to the summit of any mountain range.

Proof:

Construct a graph (the ascent graph) with vertices corresponding to configurations of the climbers where:

1) The two climbers are at the same height.

2) There is one climber on each side of the summit.

3) At least one of the climbers is at a local maxima or minima.

Join the vertices by an edge when the climbers can move between the corresponding configurations by strictly

ascending or strictly descending together.

We must show that no matter for what mountain range, the corresponding ascent graph G has a path from the

initial configuration

(

)

ZA, to the summit

(

)

MM ,.

We’ll assume no such path exists and produce a contradiction. The proof follows from two observations on G.

Observation 1: G has exactly 2 vertices of degree 1 (namely, the initial configuration and the summit), and the

rest are either degree 2 or 4 (2 when one is on a local max/min, 4 when both are on local max/min at the same

height).

Observation 2: Let

( )

(

)

GVV

ZA

∈

, denote the set of vertices that can be reached by a path from

(

)

ZA,. Note

that the summit

(

)

( )

ZA

VMM ,

,∉. It is easy to see that there are no edges in G with one end in

( )

ZA

V, and one

end in

(

)

( )

ZA

VGV,

\.

www.notesolution.com

Over 90% improved by at least one letter grade.

OneClass has been such a huge help in my studies at UofT especially since I am a transfer student. OneClass is the study buddy I never had before and definitely gives me the extra push to get from a B to an A!

Leah — University of Toronto

Balancing social life With academics can be difficult, that is why I'm so glad that OneClass is out there where I can find the top notes for all of my classes. Now I can be the all-star student I want to be.

Saarim — University of Michigan

As a college student living on a college budget, I love how easy it is to earn gift cards just by submitting my notes.

Jenna — University of Wisconsin

OneClass has allowed me to catch up with my most difficult course! #lifesaver

Anne — University of California

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.