Graphing with Vertices

Please see the attached file for the fully formatted problems. 6. Suppose G is a graph and (G)  n/3. Prove that G has one or two connected components. 7. a. Prove if n is odd, then there is no 3-regular graph with n vertices. b. Give an example of a 3-regular graph with 8 vertices. c. Prove: For every ...continues

Proofs: K-Regular Graphs

Prove that 1) If n and k are odd positive integers with k<=n-1, then there are no graphs G such that G is k-regular with order n. 2) If n is even, k is a positive integer such that k<=n-1, then there are k-regular graphs with order n.

Discrete

Let A = {1, 2, 3, 4, 5, 6,12} and define the relation R on A by m R n iff m|n. Write the definitions of the properties, reflexive, antisymmetric and transitive and the use of the definitions to determine whether each property holds for this relation. See attached file.

Discrete Math: Warshall's Algorithm

Please see the attached file for the fully formatted problems. Let A = {a, b, c, d} and let the relation R be defined on A by the matrix MR = Note, take the nodes in A in the order given Use Warshall's Algorithm to determine the transitive closure of R. Draw the digraph of the transitive closure of R and use the dig ...continues

Using the Konig-Egervary Theorem to perform a proof of matching numbers.

Use the Konig-Egervary Theorem to prove that every bipartite graph G has a matching of size at e(G)/A(G) where A(G) is the maximum degree. Use this to conclude that every subgraph of Kn,n with more than (k-1)n edges has a matching at least k.

Connectedness

Let G be a graph of order n such that deg(v)>=(n-1)/2. Prove that G is connected.

Vertex-arboricity

Let G be k-critical graph with respect to vertex-arboricity (k>=3). Prove that for each vertex v of G, the graph G-v is not (k-1)-critical with respect to vertex-arboricity.

Euler's Formula

IF G is a connected plane graph with n vertices, m edges and r regions, then n-m+r=2

Domination number

Determine (without proof) a formula for the domination number of path Pn.

Prove Connectedness

Prove that G with at least (n-1)(n-2)/2+1 edges is connected, where n is the order of G.