1
vote
1answer
19 views

Proof for the number of perfect matchings in complete graph.

I'm working on a question: Let $P_n$ be the number of perfect matchings in $K_{2n}$. Prove by mathematical induction that for each integer $n\geq1$, $P_n$ is the product of odd integers from $1$ to ...
1
vote
2answers
35 views

In complete graph, how can I prove ${n\choose 2} = {k\choose 2} + k(n-k) + {n-k\choose 2}$ for $0 \le k \le n$

I'm studying graphs in algorithm and complexity, but I'm not very good at math. How can I prove that ${n\choose 2} = {k\choose 2} + k(n-k) + {n-k\choose 2}$ for $0 \le k \le n$?
0
votes
0answers
21 views

Distance between points in the plane [duplicate]

I have this problem and I honestly don't even have a clue of how to start, would someone help me please? Let $A$ = {$v_1$,$v_2$, . . . ,$v_n$} be a set of points in the plane such that the distance ...
0
votes
1answer
68 views

Prove that the graph $H = H_1\cup H_2 = (V_1\cup V_2,E_1\cup E_2)$ is connected.

Let $G = (V,E)$ be a graph and let $H_1 = (V_1,E_1)$ and $H_2 = (V_2,E_2)$ be two connected subgraphs of $G$ that have at least one node in common. Prove that the graph $H = H_1\cup H_2 = (V_1\cup ...
0
votes
1answer
292 views

provide a combinatorial proof that $C_{n+1} = C_0C_n + C_1C_{n-1} + …. + C_kC_{n-k} + …C_nC_0$

(a) Let $C_n$ denote the number of ways of writing a valid list of open and closed parentheses of length $2n$ (valid means that at any point along the list, the number of open parentheses must be ...
1
vote
1answer
23 views

If a graph $G=\left<V,E\right>$ is connected and $\left|E\right|=\left|V\right|$ then there's a circle in $G$

Prove: If a graph, $G =\left<V,E\right>$ is connected and $|E|=|V|$ then there's a cycle in $G$ I think this should be proved by induction. This is certainly holds for $n=1$ (a vertex with ...
1
vote
1answer
26 views

Proving a graph is connected by minimum degree

Let number of vertices be >= 2. If the min degree of G >= n/2, then the graph is connected. I was trying to solve this using contradiction, but now I'm stuck. So I started out with "If the the min ...
4
votes
2answers
44 views

Prove that there is no bipartite graph on $14$ vertices with this degree sequence.

Prove that there is no bipartite graph on $14$ vertices with degree sequence: $$6, 6, 6, 6, 6, 6, 6, 6, 5, 3, 3, 3, 3, 3.$$ I assume a vertex with degree $5$ breaks this graph from being ...
0
votes
2answers
32 views

Proof d-regular graph has an equal number of vertices in its bipartition

Let $G$ be a $d$-regular graph. Suppose that $G$ is bipartite with bipartition $(A,B)$. Prove that if $d>0$ then $|A| = |B|$. Also why is this statement false when $d=0.$ I'm not sure how to show ...
1
vote
1answer
23 views

Prove that every subgraph of forest has at least one vertex of degree < 2

So I know that a forest is a graph that has no cycles. This is what I had in mind: Assume that we have the subgraph T, which has two options: to be connected or not. if it's connected it has to be a ...
0
votes
1answer
24 views

Minimum k-spanning tree including a given node

Given a Graph (V, E), it is very easy to find the minimum spanning tree using Kruskal's Algorithm. A k-minimum spanning tree is restricted to k nodes, and finding it is actually NP-hard. However, ...
2
votes
1answer
87 views

Prove that the dual graph of any (planar) graph is connected

I'd like to know if there's a standard proof that the dual graph of any planar graph is connected (or, if there's a counterexample, I'd like to know that too). I've thought of a proof that might work ...
1
vote
1answer
51 views

Show that if the diameter of an undirected graph is $d$ then there exists some vertex separator $S\subseteq V$ of size $|S| \leq { n\over d-1} $

Show that if the diameter of an undirected graph is $d$ then there is some set $S\subseteq V$ with $|S| \leq \frac{n}{d-1} $ such that removing the vertices in S from the graph would break it into ...
2
votes
1answer
63 views

Help Needed Showing that $\chi(\overline{G \times H}) \leq \chi(\overline{G}) \times \chi(\overline{H})$

Where $\chi(G)$ denotes the chromatic number, $\overline{G}$ the graph complement, and $\times$ the Cartesian Graph Product: I need to show that $(\forall G,H)( \chi(\overline{G \times H}) \leq ...
0
votes
1answer
26 views

T/F prove for modified Ramsey's theorem

By Ramsey's theorem we know that: $\forall k \in \mathbb N : \exists N \in \mathbb N$ that an arbitrary graph $G$ on a set of vertices $\{1,2,...,N\}$ contains $k$ vertices, which represent either a ...
0
votes
2answers
72 views

Prove choosing $\lceil\frac{V}{2}\rceil$ vertices accounts for at least $\frac{3}{4}$ of edges

Give a polynomial-time algorithm that finds $\lceil\frac{V}{2}\rceil$ vertices that collectively account for at least $\frac{3}{4}$ of the edges in an arbitrary undirected graph. The algorithm I have ...
1
vote
1answer
43 views

Proving breath first traversal on graphs [duplicate]

I am trying to proof the following algorithm to see if a there exists a path from u to v in a graph G = (V,E). ...
0
votes
1answer
57 views

Proofing a Reachable Node Algorithm for Graphs

I am trying to proof the following algorithm to see if a there exists a path from u to v in a graph G = (V,E). ...
1
vote
2answers
197 views

Every planar graph has a vertex of degree at most 5.

I am trying to prove the following statement, any help!? Prove that every planar graph has a vertex of degree at most 5.
1
vote
2answers
84 views

Graph Theory - Proof

I am need help to Prove the following statement: Let G be a $k$-regular graph with $n$ vertices and $k \geq 1$. Prove that $G$ does not have an independent set of size greater than $\dfrac{n}{2}$. ...
2
votes
2answers
105 views

Proving corollary to Euler's formula by induction

I'm currently looking at two proofs to the following corollary to Euler's formula and I'm not quite seeing how the authors can make a specific assumption in their proof. One proof comes from my ...
1
vote
1answer
97 views

Prove that if graph $G$ is a 3-connected planar graph then its dual must be simple.

I'm trying to study for a quiz. I think I'm on the right track with this problem, however, I'm having a difficult time formalizing it. Prove that if graph $G$ is a 3-connected planar graph then its ...
0
votes
0answers
75 views

Prove that a certain graph and its dual are 4-colorable

Let $G$ be a simple planar graph with fewer than 12 faces. Suppose that each vertex of $G$ has degree at least $3$. prove that $G$ and its dual are 4-colorable. I'm not too sure how to approach ...
1
vote
1answer
62 views

Help with proof that the union of two undirected cycle graphs is a cycle graph (with two edge deletions)

I am seeking advice on how to prove something. Apologies if my terminology is incorrect: I am not a mathematician. Let $G_1$ and $G_2$ be undirected cycle graphs with edges $E_{G1}$ and $E_{G2}$ ...
1
vote
1answer
67 views

Proving a lower bound for the traveling salesman problem

This link provides a guide for bounding solutions to the traveling salesman problem (TSP). In it, the author gives a lower bound on the optimal cost of any tour. For each vertex $v$ in the problem: ...
0
votes
2answers
83 views

Planar complete tripartite graphs

For which values of $r$, $s$, and $t$ is the complete tripartite graph $K_{r,s,t}$ planar? Obviously I want to look for either a $K_5$ or a $K_{3,3}$ in order to show that a specific graph is ...
2
votes
2answers
281 views

Help with graph induction proof

I'm trying to prove : Given a simple graph G with n vertices, where n is even, prove that if every vertex has degree n/2 + 1, then G must contain a (simple) 3-cycle. A (simple) 3-cycle is a set of 3 ...
0
votes
1answer
79 views

Proof for a graph distance

For Graph $G$, there are several $(x, y)$-paths; the shortest among them have length $2$. Thus $d(x, y) = 2$. Prove that graph distance satisfies the triangle inequality. That is, if $x,y,z$ are ...
0
votes
1answer
65 views

Simple Cycle Graph proof

How can I show/prove that given a simple graph G with $n$ vertices, where $n$ is even, that if every vertex has degree $\frac{n}{2} + 1$, then G must contain a (simple) 3-cycle
1
vote
1answer
125 views

Using Pigeonhole Principle for a graph proof

Using the Pigeonhole Principle, prove that in any graph with two or more vertices there must exist two vertices that have the same degree. (Note: the problem does not assume that the graph is ...
1
vote
2answers
55 views

Prove for a simple graph that $n-1 \leq m \leq \frac{n(n-1)}{2}$

For a given simple (that is neither loops nor multiple edges are allowed) undirected graph, where $m$ is the number of edges and $n$ is the number of vertices that the following inequality holds. ...
1
vote
0answers
299 views

Can I use Strong Induction to prove graph theory? - Hamilton Path/Tournament Graphs

I am working on the below proof. I am still new to proves so I am wondering if you guys can answer the following questions: 1) Did I use the inductive hypothesis correctly here? (By the inductive ...
0
votes
1answer
43 views

In-degree and out-degree of two distinct vertices in a directed graph

I need to prove or give a counterexample that for all $n\ge2$ there exists a directed graph of order $n$ such that every pair of distinct vertices have different out-degrees and same in-degrees.
2
votes
1answer
50 views

The rational unit distance graph is bipartite

I am trying questions from a Graph theory book by Bondy and Murty. I stumbled across a neat looking problem. The unit distance graph on a subset $V$ of $\mathbb{R}^2$ is the graph with vertex set ...
0
votes
1answer
46 views

Graphic sequence and connectivity

The question is as follows: Given the graphic sequence d=$\langle d_1,d_2,...,d_n\rangle$. Assuming $d_i\ge2$ for every i. Show that a simple and connected graph with such graphic sequence exists. ...
0
votes
1answer
39 views

Proving the number of subgraphs of $G$ isomorphic to $F$

Let $F$ and $G$ be graphs. Let $sub(F, G)$ denotes the number of subgraphs of $G$ that are isomorphic to $F$, let $inj(F, G)$ denote the number of injective homomorphisms from $F$ to $G$ and let ...
3
votes
1answer
98 views

$K_{1,3}$ packing in a triangulated planar graph

I am trying to show that every planar triangulated graph $G=(V,E)$ with $|V| \ge 5$ has an edge decomposition into $|V| - 2$ groups of $K_{1,3}$. In other words, that we can pack $|V| - 2$ instances ...
0
votes
0answers
39 views

Why does this proof need another case?

A psuedograph (with at least two vertices) is Eulerian if and only if it is connected and every evertex is even. Proof: (-->) understood so let's move on. (<--) For the converse, suppose that G is ...
1
vote
1answer
62 views

What is the proof that $\sum \limits_{v \in V} deg(v) = 2|E|$?

My textbook gives $\sum \limits_{v \in V} deg(v) = 2|E|$ and has the proof If an edge is not a loop it gets counted twice b/c it's incident with 2 different vertices. If an edge is a loop, by ...
0
votes
3answers
35 views

Prove that tree has independent set

Prove that every tree with $n$ vertices has an independent set with the size of $\lceil \frac{n} {2} \rceil$. Okay, I think I understand the concept of this whole thing. I understand, that we are ...
2
votes
1answer
486 views

Number of Hamiltonian Paths on a (in)complete graph

This question is motivated by a problem on a local programming competition (you can find the original problem statement here: http://maratona.algartelecom.com.br/files/12maratona.zip , problem E on ...
0
votes
1answer
80 views

Groetzsch Graph planarity [closed]

(1) Prove that the Groetzsch Graph is not planar.
6
votes
1answer
1k views

Proof Involving a Problem from “Good Will Hunting”

I don't know if any of you have seen the movie "Good Will Hunting" but there is a particular mathematics problem in the movie that is of interest to be. One of the problems used in the movie is "Draw ...
0
votes
1answer
59 views

Depth of BFS Tree With Different Root Nodes

I need to either prove or disprove that for any node of a graph, the depth of the BFS tree using this node as root is always the same. My intuition is that this is true, but I'm having difficulty ...
0
votes
1answer
92 views

Proof for hamiltonian cycle in grids having even no. of nodes

How can I go about proving that an undirected graph having even no. of nodes (at least one of the rows or columns are even - excluding line graphs of course) have a hamiltonian cycle? I have managed ...
1
vote
1answer
726 views

Show that a simple graph is a tree if and only if it is connected but the deletion of any of its edges produces a graph that is not connected.

I can understand why this is true--it seems really obvious--but I don't know how to formally prove this. Also, is the first part of this question this question asking us to prove that G is a tree if ...
1
vote
1answer
26 views

Prove a graph can be partitioned into two groups where every vertex has half its edges cross?

I'm trying to show that for any graph with more than 2 vertices, the graph can be partitioned into two groups such that for every vertex at least half of the vertices its connected to are in the other ...
1
vote
2answers
397 views

Prove Four Statements Are Equivalent

I have the following problem, where $G$ is a graph with $n$ vertices, prove the following statements are equivalent: 1. $G$ is connected and acyclic 2. $G$ is connected and has $n-1$ edges 3. $G$ ...
1
vote
1answer
750 views

Prove that in a simple graph there is a path from any odd vertex to any odd vertex?

Let $k$ be the number of vertices. If $k = 1$, then the point is isolated and therefore has degree 0; WLOG, we can assume that no point is isolated. With $k = 2$, there is a vertex of ...
4
votes
3answers
184 views

Proof Involving Graph Connectivity

I have the following proof: let $G$ be a graph with $n$ vertices and $n-1$ edges, prove that $G$ is connected iff $G$ has no cycles. I proceed proving "only if" first. Assume $G$ has some cycle ...