Graph Theory Theorems

First Theorem of Graph Theory (Degree Sum Formula) In any graph, the sum of ____ for |V(G)| equals ____ * |E(G)|

First Theorem of Graph Theory (Degree Sum Formula): In any graph, G, the sum of deg(v) for |V(G)| equals 2 * |E(G)|

Corollary to 1st theorem of graph theory: In any graph, the number of ODD DEGREE vertices is ____

Corollary to 1st theorem of graph theory: In any graph, the number of ODD DEGREE vertices is EVEN

If the number of vertices in a graph is n (V(G) = n), then

1) |E(G)| + |E(G’)| = nC2

2) deg_G(V) + deg_G’(V) = n-1

If the number of vertices in a graph is n (V(G) = n), then

1) |E(G)| + |E(G’)| = ___

2) deg_G(V) + deg_G’(V) = ___

Determining Isomorphism

To show graphs G and H are isomorphic: label V(G), V(H) with same labels and check that edge sets are the same

To show graphs G and H are NOT isomorphic: identify a structural characteristic that differs, justify your decisions

• degree sequences are DIFFERENT

• subgraph K_n or C_n that exists in one graph that doesn’t exist in another graph

• mapping of vertices (with degrees) not the same

• draw complements and see if they’re isomorphic

  • see if subgraphs are CONNECTED OR NOT

  • see if you can draw a bipartite graph for one and a nonbipartite one for the other

Determining Isomorphism

To show graphs G and H are isomorphic: label V(G), V(H) with ____ ____ and check that ___ are the same

To show graphs G and H are NOT isomorphic: identify a structural characteristic that differs, justify your decisions

• degree sequences are ____

• subgraph K_n or C_n that exists in one graph (does or doesn’t) exist in another graph

• mapping of vertices (with degrees) not the same

• draw ___ and see if they’re isomorphic

  • see if subgraphs are CONNECTED OR NOT

  • see if you can draw a ____ graph for one and a __ one for the other

In Complete bipartite graphs, |E(k_m,n)| = m * n

In Complete bipartite graphs, |E(k_m,n)| = _____

A graph is BIPARTITE if and only if it has NO ODD CYCLE as a subgraph

A graph is BIPARTITE if and only if it has NO __ as a subgraph

Is it possible to have 9 people in which each person knows exactly 3 others in a group? (knowing is symmetric)

NO: PROOF BY CONTRADICTION

• assume that a graph of this is possible — 9 vertices each with degree 3. By the FTGT, 9(3) = 2(E), E = 13.5 but this is IMPOSSIBLE as you can’t have ½ an edge. Therefore this scenario is NOT possible

Is it possible to have 9 people in which each person knows exactly 3 others in a group? (knowing is symmetric)

NO: PROOF BY CONTRADICTION

• assume that ___ — ___ vertices each with degree __. By the __, ( ) * ( ) = ( ) ( ) , ( ) = 13.5 but this is IMPOSSIBLE as you can’t have __ an edge. Therefore this scenario is NOT possible.

Euler’s Polyhedral formula: for any plane drawing of a connected graph with |V| vertices, |E| edges, |R| regions:
|V| - |E| + |R| = 2

Euler’s Polyhedral formula: for any ___ drawing of a ___ graph with |V| vertices, |E| edges, |R| regions:
|__| - |__| + |__| = 2

3|V| - 6 Theorem: If G is planar and |V| >= 3, then |E| <= 3|V| - 6

• not final proof that graph is not planar but if it fails, then it is inconclusive

3|V| - 6 Theorem: If G is planar and |V| >= __ , then |__| <= 3|V| - 6

• not final proof that graph is not planar but if it fails, then it is ____

2|V| - 4 Theorem: If G is planar and |V| >= 3, AND THERE ARE NO TRIANGLES, then |E| <= 2|V| - 4

• not final proof that graph is not planar but if it fails, then it is inconclusive

2|V| - 4 Theorem: If G is planar and |V| >= 3, AND THERE ARE NO ___, then |__| <= 2|V| - 4

Kurtowski’s Theorem: A graph is planar if and only if it does not contain a K₅ or K_3,3 configuration as a subgraph (ONLY WAY TO PROVE THAT IT IS NOT PLANAR)

Kurtowski’s Theorem: A graph is planar if and only if it does not contain a __ or a __ configuration as a subgraph (ONLY WAY TO PROVE THAT IT IS NOT __)

To show graph is planar: draw the graph with no edges crossing

To show graph is NOT planar:

• use the 3|V| - 6 theorem or the 2|V| - 4 theorem ; if inconclusive then:

• use kurtowski’s theorem

To show graph is planar: draw the graph with no edges crossing

To show graph is NOT planar:

• use the __|V| - __ theorem or the __|V| - __ theorem; if inconclusive then:

• use ___ theorem

An euler cycle:

1) includes every vertex and every edge of G

2) no edge appears twice

3) starting and ending vertices are the same

An euler cycle:

1) includes ___ vertex and ___ edge of G

2) no edge appears ___

3) starting and ending vertices are ___

A multigraph is eulerian if and only if it is CONNECTED and degree is EVEN for all vertices v

every edge must be visited but every vertex can be visited more than once

A multigraph is eulerian if and only if it is __ and degree is __ for all vertices v

every ___ must be visited but every ___ can be visited more than once

An open euler trail is the same as an euler cycle except the starting and ending vertices MUST BE DIFFERENT

An open euler trail is the same as an euler cycle except the starting and ending vertices must be ___

A multigraph has an open euler trail if and only if it is CONNECTED and has EXACTLY 2 vertices of odd degree

A multigraph has an open euler trail if and only if it is ___ and has EXACTLY 2 vertices of ___ degree

Necessary Condition Theorem: If G is Hamiltonian, then for every non-empty S = V(G), we have the number of components of G-S <= |S|

prove graphs are NOT hamiltonian

converse of this theorem is FALSE

Necessary Condition Theorem: If G is Hamiltonian, then for every non-empty S = V(G), we have the number of components of G-S ___

prove graphs are ___ hamiltonian

converse of this theorem is TRUE/FALSE

Sufficient Condition Theorem: IF G is a graph with n>= 3 vertices and deg(u) + deg(v) >= n for EVERY PAIR of non-adjacent vertices u, v, then G is Hamiltonian.

use to show G IS hamiltonian

converse of this theorem is FALSE

Sufficient Condition Theorem: IF G is a graph with n>= 3 vertices and deg(u) + deg(v) __= n for ___ of ___ vertices u, v, then G is Hamiltonian.

use to show G ___ hamiltonian

converse of this theorem is TRUE/FALSE

A graph G is Hamiltonian if it contains a cycle, C_n that includes EVERY VERTEX of G. Such a cycle is called a Hamiltonian cycle

every vertex can only be visited once, but NOT every edge has to be used.

A graph G is Hamiltonian if it contains a cycle, C_n that includes ____ of G. Such a cycle is called a ___ cycle.

every vertex can ONLY be visited __, but NOT every __ has to be used.

Statement S: If A then B

Contrapositive of S: If not B then not A

Converse of S: If B then A

If and only if: A iff B means:

• if A then B

• if B then A

Statement S: If A then B

Contrapositive of S: If ___ then ___

Converse of S: If __ then __

If and only if: A iff B means:

• if __ then __

• if __ then __

Negations:

• if A or B → not A and B

• if A exists → A does NOT exist

• every → at least 1/some

Negations:

• if A or B → __

• if A exists → __

• every → __

Check for Eulerian

If graph is Eulerian: draw the euler cycle

If a graph is NOT eulerian: show that it has an odd degree vertex

Check for Eulerian

If graph is Eulerian: draw the __ cycle

If a graph is NOT eulerian: show that it has an ___ degree vertex

Check if a graph is Hamiltonian

If graph is hamiltonian: use sufficient condition theorem if graph is hard to draw OR draw the hamiltonian cycle on the graph

If a graph is NOT hamiltonian: use necessary condition theorem

Check if a graph is Hamiltonian

If graph is hamiltonian: ___ theorem if graph is hard to draw OR draw the ___ cycle on the graph

If a graph is NOT hamiltonian: use___ ___ theorem

If graph T is a tree, and if a leaf V is removed from T, the graph T-V is also a tree

If graph T is a tree, and if a __V is removed from T, the graph T-V is also a ___

All trees have leaves

All trees have ___

If T is a tree, then E(T) = |V(G)| - 1

If T is a tree, then |E(T)| = |___| - ___

If a graph has components G1, G2, G3, … GK, then X(G) is the biggest X(G) of the component coloring

If a graph has components G1, G2, G3, … GK, then X(G) is the ___ X(G) of the component coloring

Any tree has a maximum of n-1 leaves and a minimum of 2 leaves (provided n>2)

Any tree has a maximum of ___ leaves and a minimum of __ leaves (provided n>2)

4 Color Theorem: every planar graph G has at MOST X(G) = 4

4 Color Theorem: every planar graph G has at MOST X(G) = __

5 color theorem if G is a planar graph than X(G) <= 5

5 color theorem if G is a planar graph than X(G) <= __