MASTER CARDS Discrete Math II - Fall 2025 Study Guide

reflexive

EVERY element in a given set MUST be related to itself. EVERY.

irreflexive

EVERY element in a given set must NOT related to itself. EVERY.

neither reflexive nor irreflexive

if some elements in the set are a mix of being reflexive and irreflexive

symmetric

xRy IFF yRx ; arrows either must have a partner or no partner at all

antisymm

for every pair if x is NOT equal to y, then either xCy or yCr is true, but not both at the same time ; either one arrow or none

transitive

IFF for every 3 connected elements there must be a way to get to all 3 already established

a walk has to be ____ before anything else

valid

trail

a walk with no rep e’s

path

an open walk with NO REP V’s

circuit

a closed walk with no repeating e’s

cycle

a closed walk with no repeating edges OR vertices

• whose length is at least 1

equation to find the total degree of a graph

deg = 2 * |E|

graph isomorphism qualities

• same number of vertices

• same number of edges

• same degree sequence

a relation R on A is a PARTIAL ORDER if…

is its reflexive, anti-symmetric, and transitive

total order

means any pair of elements are compatible

in a hasse diagram, what is assumed?

reflexivity and transivity

a equivalence relation of R is…

reflexive, symmetric, and transitive. denoted a ~ b

ex: you have the same bday as yourself. if you and jackie have the same bday, and jackie has the same bday as maria, then you have the same bday as maria

simple graph

a graph that doesnt have parallel edges or self-loops

adjacent def

an edge between two vertices exists

neighbor def

edge a is a neighbor to edge b if there is an existing edge bewteen the two

degree of a vertex

the number of neighbors a given vertex has

total degree

the sum of the degrees of all of the vertices. is equal to the number of edges present multiplied by 2

in a regular graph, all of the vertices have the same degree. In a d-regular graph, all the vertices…

…have a degree of d

graph A is a subgraph of graph B if…

both the vertices and edges in graph A are subsets(aka present) of graph B

bijection rule

if there is a bijection from one set to another, then the two sets have the same cardinality

Let S and T be two finite sets. If tehre is a bijection from S to T, then |S| = |T|

connected components

• write in undirected notation {}

• separate with commas

• enclose with another set of curly brackets

are the maximal set of connected vertices and all the edges between any two of them in a set

ex: {{1,2,3},{4,5},{6}}

euler circuit

a closed walk with NO REP E’S that contains EVERY VERTEX

euler trail

a walk w NO REP E’S that contains EVERY EDGE VERTEX

in a euler trail, exactly ___ vertices have odd degrees

two; one must be at the end and the other must be at the front

hamiltonian cycle

a closed walk with NO REP E’S OR V’S that includes EVERY VERTEX in the graph

hamiltonian path

an open walk with NO REP V’s that includes EVERY vertex in the graph

a h.cycle can be transformed into an h.path by…

…deleting the last vertex

if a graph has a h.cycle, then it also has a…

…h.path

as long as a graph has atleast ONE planar embedding…

..then it is planar!

if n is >= 3, then m MUST be <= 3n-6

n = vertices

m = edges

if this inequality fails, then G is NOT planar

ways to DISPROVE isomorphism

• diff # of edges

• diff # of vertices

• diff # degree sequences

ways to PROVE isomorphism

• matching degree sequences

• match vertex-to-vertex

in an adjacency rep, you must list in ascending order, and list vice versa

true