Tagged Questions

35 views

IS this proof by induction of the hand shake lemma correct?

Proof by induction that the sum of degrees of vertexes in an undirected graph equals two times the number edges, where $V$ is the set of vertexes and $E$ is an edge multiset: \sum_{v ∈ V} deg(v) = ...
40 views

The maximum no. of edges in a DISCONNECTED simple graph…

... on n vertices when it is not connected being equal to (1/2)(n - 1)(n - 2)... I can see that for n = 1 & n = 2 that the graphs have no edges... however I don't understand how to derive this ...
160 views

Help showing that every walk of length $k$ from $x$ to $y$ in a graph is a path.

If I were to suppose $x$ and $y$ are two vertices in the same connected component of a graph, and let $k$ be the distance between them, how would I prove that every walk of length $k$ from $x$ to $y$ ...
36 views

An undirected graph $G$ can be decomposed into simple edge-disjoint cycles if and only if all of its vertices have even degree.

Research effort: $\rightarrow)$ I think this is relatively easy. $\leftarrow)$ Let $G = (V,E)$, let $w$ be any vertex of $G$, given that all the vertex have even degree, I'm assured that I can ...
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 ...
47 views

Proof involving maximum weight of edge in minimum spanning tree

Let $G$ be a minimum spanning tree of a complete graph. Let $e$ be the maximum weight edge in $G$. I'd like to proof that given any other spanning tree $G'$ of this graph, being $j$ the maximum weight ...
47 views

Proof for binary tree is a planar graph

Suppose G is a binary tree. Is G necessarily planar? Give a proof, or a counterexample. My guess is that it is indeed planar but I am struggling to find a formal proof for this. EDIT: Is there a ...
27 views

Proof homomorphism between graphs

Given two graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$, an homomorphism of $G_1$ to $G_2$ is a function $f:V_1 \rightarrow V_2$ such $(v,w) \in E_1 \rightarrow (f(v),f(w)) \in E_2$. We establish that ...
27 views

Proof that a local minimum in a spanning tree is also a minimum spanning tree.

Be $G$ a connected graph with weights associated to its edges. Be $T(G)$ the graph that has the spanning trees of $G$ as vertex, and two spanning trees are adjacent to each other if and only if each ...
83 views

If a connected graph has a unique spanning tree, then it is a tree.

Prove if a connected graph has a unique spanning tree, then it is a tree. Edit: This can be shown with proof by contradiction.
29 views

Let $G$ be a graph with radius $r$ and let $x$ be a vertex in the center of $G$. If $d$($x,y$)=$r$, then $y$ is in the periphery of $G$

Prove, disprove, or give a counterexample: Let $G$ be a graph with radius $r$ and let $x$ be a vertex in the center of $G$. If $d$($x,y$)=$r$, then $y$ is in the periphery of $G$. Eccentricity - the ...
44 views

Proof that any self-complementary graph has to have $4k$ or $4k+1$ vertex, for some $k \in \mathbb N$

I've seen looking on previous questions that using this algorithm, I can construct self-complementary graphs. I got confused at this point, because I'm not sure if I should proof that there are no ...
40 views

Finding quantity of vertex of odd degree in a graph

Let $G=(V,X)$. If $G$ has n vertex, such exactly $n-1$ have odd degree, how many vertex of odd degree have $\overline {G}$. ($\overline {G}$ the complement of $G$.) So the first thing I notice is ...
16 views

Proof that in a graph of $2$ or more vertrex, there's at least $2$ of them that have the same degree

That's what I what to prove let $G$ be an undirected graph such it has $2$ or more vertex, there's at least $2$ vertex that have the same degree. I'm almost certain that, supposing that it's possible ...
54 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). ...
65 views

Let $G$ be a connected graph. If $G$ has no cut vertices, then G has no bridges.

Prove, disprove, or give a counterexample: Let $G$ be a connected graph. If $G$ has no cut vertices, then $G$ has no bridges.
30 views

If the edge $xy$ is a bridge of $G$, then $x$ and $y$ are in separate components of $G$-$xy$.

If the edge $xy$ is a bridge of $G$, then $x$ and $y$ are in separate components of $G$-$xy$. I can't think of a counterexample so I am operating under the impression that it can be proved. How does ...
70 views

Prove that a graph with $n$ vertices and less than $n$-1 edges, is disconnected.

Prove that if $G$ is a graph with $n$ vertices and fewer than $n$-1 edges, then $G$ is disconnected. The book I am working through uses a similar definition of "$n$ vertices and at least $n$-1 edges, ...
24 views

Proving a circuit of a graph will have an edge in common with a cycle of the same graph.

Prove, if possible, if an edge lies on a circuit in $G$, then the edge also lies on a cycle in $G$. I attempted to find a counterexample but it seems pretty evident that this statement is true. The ...
101 views

Finding minimum graph of $k$ disjoints component

Sorry for the english, I tried to make it the most clear possible. Be $G$ a connected graph not directed, I have to find an algorithm that given $n$ the quantity of vertex and $0<k<n$ disjoint ...
71 views

Spanning trees in planar dual graph

The amount of spanning trees in a planar graph G is equal to the amount of spanning trees in the dual graph G*. I would like to proove this, i know it's true, but i would like to show that it holds ...
78 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 ...
87 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 ...
74 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 ...
240 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 ...
67 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 ...
86 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 ...
51 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. ...
59 views

Prove thoroughly: If the degree of all vertices is greater or equal to $\frac{|V| - 1}{2}$, then the simple graph is connected.

I am struggling to write a good, thorough proof. The proof is supposed to be logically rigorous, correct and complete (e.g. no hidden assumption). Moreover, style is important - the proof should be ...
48 views

Proof of the Surfer Model Pagerank formula

How do you prove this formula for the Surfer Pagerank algorithm mathematically? ...
708 views

Can an algorithm be part of a proof?

I am an undergraduate student. I have read several papers in graph theory and found something may be strange: an algorithm is part of a proof. In the paper, except the last two sentences, other ...
53 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 ...
270 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$ ...
66 views

Are these two proofs regarding coloring valid and complete?

Question #1) Prove or disprove: If G is a graph and for every vertex $v \in V(G), \chi (G-v) < \chi (G)$, then for every subgraph H such that $H \neq G, \chi(H) < \chi(G)$. Question #2) Prove ...
1k 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 ...
87 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 ...
31 views

Is this graph transitive?

I have a graph $G = (A,B)$ which is transitive when: $(a,b) ∈ B ∧ (b,c) ∈ B → (a,c) ∈ B$. How can I prove that $G$ is transitive iff it's acyclic?
17 views

Question about graphs and relations

If I have a directed graph $G = (V,E)$, let the relation $R$= {$(a,b)$ | $a$ has a directed path to $b$} be a relation over $V$. How can I prove that $R$ is an equivalence relation, partial order, ...
50 views

If $G$ is disconnected and the vertices $x,y$ are adjacent in $G$, then there is a vertex that isn't adjacent to $x$ and isn't adjacent to $y$.

I'm just starting graph theory and I'm trying to prove the following: Let $G$ be a simple disconnected graph with vertex set $V(G)$ and edge set $E(G)$. If $x,y\in V(G)$ and $xy \in E(G)$, then ...
82 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)?
197 views

$G$ is a tree $\iff G$ contains no cycles, but if you add one edge you create exactly one cycle - is my proof correct?

$G$ is a tree $\iff G$ contains no cycles, but if you add one edge you create exactly one cycle Could anyone please be so kind to check my proof? That would be very much appreciated. Thank you in ...
428 views

Proof the sum of the square of the in and out degree are the same [duplicate]

I know by the handshaking theorem that in a graph, the sum of the in degree and the sum of the out degree will be the same. I observe that in a complete directed graph (as in a complete graph that has ...
215 views

maximum number of edges to be removed to possess a property

I am working on a problem. We know that on squaring a cycle, degree of every vertex is 4. For squares of cycles, we know if we delete any arbitrary edge then still eccentricity is same for all ...
88 views

eccentricity in vertex transitive graphs

I am trying to prove the following.. If $G$ is a veretx transitive graph, then how can we prove that eccentricity of every vertex is same? Getting no idea from where to start? How to prove the same ...
82 views

Why no cut-vertices or cut edges in a graph where eccentricity is same for all vertices

I need help to prove the following statement. There are no cut-vertices or cut-edges(bridges) in a graph where eccentricity is same for all vertices. I am getting that if the graph contains a ...
275 views

The Dinitz Problem - proof

This theorem is the one that the proof is for Consider $n^2$ cells arranged in an $(n × n)$-square, and let $(i, j)$ de- note the cell in row $i$ and column $j$. Suppose that for every cell ...
799 views

Checking if my proof for path and walk in graph theory is correct

I am trying to prove that if there exists a walk in a graph from $v$ to $w$, then there exists a path in the graph from $v$ to $w$ where $v$ and $w$ are vertices of graph $g$... I am not sure if I ...