Key Theorems

Question 1

Hall’s Marriage Theorem

Answer 1

A bipartite graph T with vertex sets X and Y contains an X-complete matching if and only if for every subset A of X the number of vertices joined to A is greater or equal to the number of vertices in A

Question 2

Index of H in G

Answer 2

The index of H in G, denoted by [G:H] is the number of left (or right) closets of H in G

Question 3

Lagrange’s Theorem (Equation)

Answer 3

IGI = [G:H]IHI

Question 4

Lagrange’s Theorem

Answer 4

Let G be a finite group, and H is a subgroup of G. Then:
1) The order of H divides the order of G
2) The index of H in G is the number of distinct left (or right) closets of H in G and satisfies (Lagrange’s Equation)

Question 5

Cyclic Group

Answer 5

A group G is cyclic if there exists an element g in G (called a generator) such that every element of G can be written as power (or multiple) of g

G = <g> = (0, g, 2g, ….., (n-1)g)</g>

Question 6

Path (length k between vertices)

Answer 6

A path of length k from vertex v to vertex w is a sequence of vertices {v = w0, w1, ……, wk = w} s.t each {wi, wi+1} is an edge

Question 7

Eulerian Graph

Answer 7

A graph is Eulerian if it possess an Eulerian circuit (circuit where every edge is used exactly once) - all even vertices

Question 8

Semi-Eulerian Graph

Answer 8

A graph is semi-Eulerian if it possesses an Eulerian path (path where every edge is used exactly once) - exactly 2 vertices of odd degree

Question 9

Complete Graph

Answer 9

A graph where every vertex connects with every other vertex

Question 10

Bipartite Graph

Answer 10

A graph where the vertex sets can be partitioned into 2 sets, X and Y, s.t all edges are between vertices in X and Y

Question 11

Matching in Bipartite Graph

Answer 11

A matching in a bipartite graph is a set of edges M if no two edges in M have a common vertex

Question 12

Graph

Answer 12

A graph T = (V,E) is a pair of a (finite) set V of vertices and a set E of unordered pairs of vertices, called edges

We define the size of T to be its number IEI of edges

Question 13

Adjacency

Answer 13

We say that vertices an and b are adjacent if {a,b} is an edge. In that case,k we say a,b are incident to the edge {a,b}

Question 14

Weighted Graph

Answer 14

A weighted graph (T,w) is a graph T=(V,E) with an associated weight function w:E - R, that assigns a weight to each edge

Question 15

Hamiltonian Path

Answer 15

A path is called a Hamiltonian path if it uses each vertex exactly once

Question 16

Order

Answer 16

Written IGI, is the number of elements in G (may be finite or infinite)

Question 17

Cyclic

Answer 17

A group G is a cyclic group if there exists x in G s.t G is equal to <x></x>

Question 18

Eulerian Path (in a graph)

Answer 18

A graph has a circuit which passes through each edge exactly once if it is connected and every vertex has an even degree