After Midterm

Question 1

Simple Graph

Answer 1

A simple graph G =(V,E) consists of a non-empty set of Vertices V and a set E of unordered pairs of distinct elements of V called edges

Question 2

Multigraph

Answer 2

When a graph allows multiple edges between pairs of vertices, we call it a multigraph.

Question 3

Pseudograph

Answer 3

A multigraph that allows for loops

Question 4

Directed Graph

Answer 4

A directed graph G = (V,E) that consists of a non-empty set of vertices V and a set E of ordered pairs of distinct elements of V called edges.

Question 5

Order

Answer 5

of vertices (Typically n)

Question 6

Size

Answer 6

of edges (Typically m)

Question 7

Max # edges for simple graph

Answer 7

n choose 2 = (n(n-1))/2

Question 8

Max # edges for direct graph

Answer 8

n^2

Question 9

Same degree theory

Answer 9

In a simple graph of n>1 vertices, there is always two vertices with the same degree

Question 10

(u,v) in an edge in a directed graph

Answer 10

u is adjacent to v

v is adjacent from u

Question 11

Handshaking Theorm

Answer 11

If you divide the sum of the degrees of a simple graph by 2 you get the number of edges

Question 12

Bipartite Graph

Answer 12

A simple graph is bipartite if the set vertices V can be split into two sets V1 and V2 such that all edges have one endpoint in V1 and one in V2.

Question 13

Matching

Answer 13

A matching is a subset of edges such that no two edges are incident with the same vertex

Question 14

Maximum Matching

Answer 14

A matching with the largest amount of edges possible

Question 15

Subgraph

Answer 15

A subgraph of G = (V, E) is a graph G = (W,F) such that W is a subset of V and F is a subset of E.

Question 16

Induced Subgraph

Answer 16

An induced subgraph has the same properties as a subgraph, although additionally, all edges between two vertices in the subgraph must be present if they are in the original.

Question 17

Isomorphism

Answer 17

Two simple graphs G1 = (V1,E1) and G2 = (V2,E2) are isomorphic if there is a one-to-one and onto function from V1 to V2 such that edge (u,v) is in E1, if and only if (f(u),f(v)) is in E2 for all edges.

Question 18

Path

Answer 18

A path is a sequence of vertices V0,V1…Vn where there is an edge between each consecutive pair of vertices

Question 19

Simple Path

Answer 19

A path that doesn’t contain the same vertex more than once

Question 20

Cut Vertex

Answer 20

A vertex is a cut vertex if the removal of it and its incident edges leaves the graph disconnected

Question 21

Vertex Cut

Answer 21

A subset V1 of V such that G-V1 is disconnected

Question 22

Directed Graph: Strongly Connected

Answer 22

There is a path from (u,v) and (v,u) for every pair of vertices.

Question 23

Directed Graph: Weakly Connected

Answer 23

The graph is connected when direction is removed

Question 24

Euler Path

Answer 24

A path that traverses every edge exactly once in an undirected graph (Two vertexs of odd degree)

Question 25

Euler Cycle

Answer 25

A cycle that traverses every edge exactly once (Starts and ends at the same vertex)
(All vertexs of even degree)

Question 26

Hamilton Path

Answer 26

A path that visits every vertex exactly once

Question 27

Hamilton Cycle

Answer 27

A cycle that visits every vertex exactly once (Except the first and last…. starts and ends at the same vertex).

Question 28

Hamiltonian

Answer 28

If a graph contains a Hamilton cycle it is hamiltonian

Question 29

Dirac’s Theorem

Answer 29

If G is a simple graph with n>2 vertices such that each vertex is at least n/2, then G is Hamiltonian.

Question 30

Ore’s Theorem

Answer 30

If G is a simple graph with n>2 vertices such that deg(u) +deg(v) >= n for every pair of non-adjacent vertices u and v, then H is hamiltionian

Question 31

Planar

Answer 31

A graph is planar if it can be drawn on a plane without any edges crossing

Question 32

Euler’s Formula

Answer 32

If G is a connected planar simple graph with n vertices and m edges and if r is the # of regions in the planar representation of G, then r = m-n+2

Question 33

Properties of planar graphs: Corollary 1

Answer 33

If G is a connected planar simple graph, with n>=3 vertices and m edges, then m <=3n-6

Question 34

Properties of planar graphs: Corollary 2

Answer 34

If G is a connected planar simple graph, then G has a vertex with degree <=5

Question 35

Homeomorphic

Answer 35

Two graphs are homeomorphic if they can be obtained from the same graph by a sequence of subdivisions.

Question 36

Kuratowski’s Theorem

Answer 36

A graph is non-planar if and only if it contains a subgraph homeomorphic to K5 or K3,3

Question 37

Four Colour Theorem

Answer 37

A planar graph or map has a chromatic # of 4 or less

Question 38

Spanning Tree

Answer 38

A subgraph of a connected simple graph G that is a tree containing every vertex of G

Question 39

Minimum Spanning Tree (MST)

Answer 39

When edges are weighted, MST of G is the spanning tree where total weight (sum of weights of its edges) is the minimum possible.

*If all edge weights are unique, then there is a unique MST