Scribd
Upload
3 views33 pages

Graphs and Trees in Discrete Mathematics

Uploaded by

Jeselle Barrion
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
3 views33 pages

Graphs and Trees in Discrete Mathematics

Uploaded by

Jeselle Barrion
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Discrete Mathematics

Week 15
Graph and Trees
Drawings such as those shown previously are
illustrations of a structure known as a graph. The
dots are called vertices (plural of vertex) and the
line segments joining vertices are called edges. As
you can see from the drawing, it is possible for two
edges to cross at a point that is not a vertex. Note
also that the type of graph described here is quite
different from the “graph of an equation” or the
“graph of a function.”
Exercises
1. Define this graph formally by specifying its vertex set,
its edge set, and a table giving the edge-endpoint
function.
Exercises
2. Draw picture of Graph G that has vertex set {v1, v2, v3,
v4, v5} and edge set {e1, e2, e3, e4}, with edge-endpoint
function as follows.
Exercises
3. Find all subgraphs of each of this graph.
Exercises
4. Recall that Km,n denotes a complete bipartite graph on
(m, n) vertices. Draw K4,2
5. Which of the following graphs are bipartite?
Answers
1.
Answers
2.
Answers
3.
Answers
4.

w1

w2
Answers
5. a. Yes, b. No

You might also like