School

Ball State UniversityDepartment

Mathematical SciencesCourse Code

MATH 215Professor

AllStudy Guide

MidtermThis

**preview**shows half of the first page. to view the full**2 pages of the document.**Maths 215 Exam II Review Sheet

⋄READ THE BOOK. Re-read every section of the covered material.

⋄Re-do all the homework problems (don’t just look over your old solutions).

⋄Know the following terms and symbols and how they are used.

•Undirected/Directed graph (via diagram and formal

deﬁnition)

•Vertices and Edges

•Loops and Multiple edge

•Degree/indegree/outdegree

•Path/cicuit

•Connected

•Euler path/circuit (ﬁnd them when they exist)

•Hamilton path/circuit (ﬁnd them when they exist)

•Graph coloring

•Planar graph

•Four color Theorem

•Network and weighted edges

•Binary search tree

•Root node

•Children

•Simple graph

•Simple path

•Complete graph

•Set theory notation

•Set builder notation

•Be able to translate between set theory notation and

logic notation

•Symbols ∈,⊆, /∈, , ∪,∩,′,\(set diﬀerence)

⋄Note that 5 ⊆Nis False, but 5 ∈Nis True.

•Universal set

•Cartesian product – use {} and () properly.

⋄Ex. {0,1} × {a} ̸={{0, a},{1, a}},

but {0,1} × {a}={(0, a),(1, a)}

•Power set

•DeMorgan’s Laws for sets

•Inclusion-exclusion principle

•What is the structure of a proof to show A⊆B?

C=D?

•Function, domain, codomain, well-deﬁned, one-to-one

function, onto, injection, surjection, bijection, one-to-

one correspondence, image

•What is the structure of a proof to show a map is

onto? one-to-one?

•Inverse of a function

•Restriction of a function

•Composition of functions

•Relation

•Reﬂexive, symmetric, transitive, anti-symmetric

•Represent a relation via a graph

•Partition and equivalence relation (and their connec-

tion)

•Equivalence classes

•Modular arithmetic

•Partial order and total order

•Poset

•Hasse Diagram and topological sorting

•Maximal/minimal elements

•Isomorphic graphs

•Theorems related to degree counting, Euler circuits

•Tree (depth of vertex and height of tree)

Know and be able to apply the following theorems

of Euler:

1. In any graph, the sum of the degrees of the vertices

equals twice the number of edges. (Theorem 2.6)

2. If a graph has more than two vertices of odd degree, it

does not have an Euler path. (Theorem 2.12, HW # 18

in 2.6)

3. If a connected undirected graph has exactly two

vertices, vand w, of odd degree, then there is an Euler

path from vto w. (Theorem 2.11, HW # 17 in 2.6, text

mistakenly omitted adjective undirected)

4. If all the vertices of a connected undirected graph

have even degree, then the graph has an Euler circuit.

###### You're Reading a Preview

Unlock to view full version