2
votes
2answers
28 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
31 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
57 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
57 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
27 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
34 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
155 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
26 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
31 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
59 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
44 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
104 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
22 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
35 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
33 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
26 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
80 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
35 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
60 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
32 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
175 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
78 views

Groetzsch Graph planarity [closed]

(1) Prove that the Groetzsch Graph is not planar.
5
votes
1answer
323 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
43 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
51 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 ...
0
votes
1answer
439 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
23 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
219 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
595 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
167 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 ...
2
votes
1answer
272 views

Proof Involving Connected Components of a Graph

I have the following problem: prove that every graph with $n$ vertices and $n-k$ edges has at least $k$ connected components. I have approached this proof using induction, but am having difficulty ...
0
votes
1answer
38 views

Proof Involving Simple Graph

I have the task of proving that if there is a simple graph with 6 vertices and 13 edges, there is at least one vertex of degree greater than or equal to five. Given that, $2m = \sum_{v\epsilon V} ...
0
votes
1answer
61 views

$R\subset S\times S$ for $S=\{1,2,3\}$: A Graph-Theoretic Approach

So I am given the relation $R=\{(1,1),(2,2),(3,3),(1,2),(1,3)\}$ and asked which of the properties reflexive, symmetric, or transitive are held in the relation, but what I am thinking is that this can ...
1
vote
1answer
794 views

Solving graph theory proofs

I am trying to study for an exam on graph theory and I have a few questions. How would you start a proof? For example, when I see a problem like this: Let G be a graph with n vertices where every ...
0
votes
1answer
76 views

how to prove a result

I was studying about graph operation on wiki. Corona product of graphs $G_1$ and $G_2$, is the graph which is the disjoint union of one copy of $G_1$ and $|V_1|$ copies of $G_2$ ($|V_1|$ is the number ...
1
vote
2answers
288 views

Dijkstra's Shortest-Path Algorithm

I'm presented with the following algorithm: Dijkstra's Shortest-Path Algorithm This algorithm finds the length of a shortest path from veftex $a$ to vertex $z$ in a connected, weighted ...
0
votes
1answer
105 views

Solving the travelling sales person problem for the graph.

If I'm asked to "[s]olve the travelling sales person problem for the graph," am I asked to just find it manually? If not I could write some code to find the answer if I had a way to catalog the ...
2
votes
1answer
148 views

Show that if $n\geq 3$, the complete graph on $n$ vertices $K_n$ contains a Hamiltonian cycle.

I'm asked the following quesiton: Show that if $n\geq 3$, the complete graph on $n$ vertices $K_n$ contains a Hamiltonian cycle. This seems obvious since $K_n$ contains a subgraph which is a ...
1
vote
1answer
101 views

A Simple Graph: A Simple non-Hamiltonian Proof

How does one show that the following graph has no Hamiltonian cycle? From N.S.'s comment I get that the problem really just reduces to the following simpler problem: Actually, if you ...
0
votes
2answers
79 views

non-Hamiltonian Cycles: How to Prove for Small Graphs

How do I prove that the following graph is a non-Hamiltonian cycle? $\hspace{5.3cm}$ I'm asked to create a graph which is both non-Eulerian and non-Hamiltonian, and this is what I produced in TiKz. ...
0
votes
0answers
75 views

Hamiltonian cycle problem: how to prove NP-completeness?

How to prove that finding a Hamiltonian cycle in a graph is an NP-complete problem? Should I try to reduce the travelling salesman problem (TSP) to this one (Hamiltonian cycle)?
2
votes
1answer
410 views

How to show a graph is not Hamiltonian?

Suppose you are given a graph $G$ with the properties that $G$ is 3-regular, $v_G = 10$ where $v_G$ is the number of vertices in $G$, and girth$(G) \geq 5$. How can you tell that $G$ is not ...
1
vote
2answers
137 views

Theorem of Eulerian Path

I am a little bit confused by the proof of Theorem 1.8.1 (Euler 1736) on the page 23 of the textbook Graph Theory by Diestel. Theorem 1.8.1 (Euler 1736) A connected graph is Eulerian if and only if ...
0
votes
0answers
25 views

Second-Order Random Choice Proof

Given $G = (V,E)$ ;$ |V| = n, |E| = m$ then choose $T$ with $t$ vertices uniformly I have to proof the graph theory as $$E[X] - E[Y] \geq a$$ Which $$E[X] \geq \frac{(2m)^t}{n^{2t-1}}$$ X is random ...
2
votes
3answers
359 views

Proof that a n-hypercube is n-vertex-connected

I'm new to graph theory, I'm finding it hard to get upon proofs. To prove: An n-hypercube is n-vertex connected. Approaches I thought: It holds true for n=2, so ...
4
votes
3answers
679 views

Short proof for the non-Hamiltonicity of the Petersen Graph

It is well known that the Petersen Graph is not Hamiltonian. I can show it by case distinction, which is not too long - but it is not very elegant either. Is there a simple (short) argument that the ...
3
votes
2answers
192 views

If a graph has no isolated or pendant vertices then it contains at least one simple circuit

I am trying to prove that if a finite graph has no isolated or pendant vertices then it contains at least one simple circuit. Let the graph with no isolated or pendant vertices be $(V,E)$. A path in ...
2
votes
1answer
154 views

Connected Components Graph proof

I am trying to do this one problem for a homework set, and am not entirely sure how I would even start this proof. Here is the question Prove, by induction on k, that a connected component of k nodes ...
2
votes
2answers
101 views

Prove that if you have 2 trails of max length possible, in a connected graph, then them share a vertex.

What I'm wanting to prove is what it says in the title of the question. Or more formally: $P=(V_p,E_p)$, $Q=(V_q,E_q)$ are two trails of the max length possible / G=(V,E) a connected graph, $(V_p ...
4
votes
0answers
210 views

Combinatorics and graph theory - counting connected graphs

We denote by $C(n,n+k)$ the number of connected graphs on $n$ vertices with $n+k$ edges. I have 2 problems I wish to prove, but after much effort have gotten nowhere with. I would greatly value some ...