Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

4
votes
3answers
200 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 ...
3
votes
1answer
58 views

A bipartite graph question

Is there a bipartite graph with degrees $3,3,3,3,3,3,3,3,3,5,6,6$? I've been stuck attempting to draw this graph but keep getting lost. I think it is no, but I am not concrete about it. Is it no?
1
vote
1answer
201 views

bipartite graph matching

can anybody please give me a hand on this lemma on bipartite graph matching please? Let M1 and M2 be two arbitrary matchings in a bipartite graph G with bipartition {P,Q} (of its vertex set). Prove ...
1
vote
1answer
191 views

Form of characteristic polynomial of a bipartite graph

Apparently, it is true that the characteristic polynomial of a bipartite graph takes the form $g(t^2)$ for an even number of vertices and $tg(t^2)$ for an odd number of vertices for some polynomial ...
2
votes
1answer
158 views

Graph Theory involving bipartite graphs

A bipartite graph has 16 nodes of degree 5, and some nodes of degree 8. We know that all degree-8 nodes are on the left hand side. How many degree 8 nodes can the graph have? Hi, I am having trouble ...
2
votes
1answer
506 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 ...
1
vote
0answers
56 views

Types of symmetry for combinatorial graphs

Let $G$ be an undirected, connected graph without loops. Let's call $G$ symmetric iff it has a non-trivial automorphism (that is a permutation $\pi : V(G) \rightarrow V(G) $ – which is not the ...
2
votes
1answer
250 views

Graph theory: spanning tree diameter

For $2 \le k \le n − 1$, prove that the $n$-vertex graph formed by adding one vertex adjacent to every vertex of $P_{n−1}$ has a spanning tree with diameter $k$. I know that the diameter of a ...
0
votes
1answer
187 views

simple connected but not complete graph has an induced path of length 2.

Let $G$ be a simple connected but not complete graph. Show that $G$ has an induced path of length $2$. This is my argument so far. I think I've very close but I just need a little push in the ...
0
votes
1answer
99 views

Number of subgraphs of diameter d

I have a graph $G(V, E)$. I want to know the number of unique subgraphs with diameter d >= 1. I will give a couple of examples: 1) In the following graph, there is 3 unique subgraphs of diameter 1. ...
1
vote
1answer
631 views

Transitivity of Relations and Eulerian Cycles

Question: Let $R$ be the relation $\{(1,1),(2,3),(2,2),(3,2),(3,3)\}$ on the set $S=\{1,2,3\}$. Is $R$ an equivalence relation? If $R$ is, describe the partition $\mathscr{P}$ determined by $R$ by ...
0
votes
1answer
55 views

Diffusion on a weighted graph

I have a weighted graph and want to apply a diffusion step to it. I read this paper, where they formulate such a diffusion step for unweighted graphs: $Z_i(t+1)=Z_i(t)+\alpha\sum_j ...
0
votes
1answer
81 views

Proving a graph must be connected [duplicate]

Let $G$ be a graph with $n$ vertices and $e$ edges such that $e>\binom{n-1}{2}$. Then $G$ must be connected. As usual, hints would be greatly appreciated. If it where$\binom{n}{2}$ then wouldn't ...
0
votes
1answer
55 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} ...
13
votes
3answers
384 views

Metal Ball Cage Template Cardinality: A Brilliantly Lazy PROOF

N.B. - I'm looking for the simplest way to ascertain the number of templates $T$ (see below) comprising the structure from just one angle alone; that is, I'm sitting down looking up at this thing, ...
3
votes
1answer
173 views

Number of isomorphism classes of countable models of a theory

Whether there are countably or uncountably many isomorphism classes of countable models of a given theory depends on the theory: if the theory is strong enough, there will be only countably many ...
2
votes
2answers
260 views

Minimum number of colors

I just read an old book today and it was stated that mathematicians are still unable to answer "What is the minimum number of colours needed to paint a map such that adjacent countries will not have ...
2
votes
2answers
62 views

Generalizations of colorability

It is fun to recognize that the $n$-colorable graphs are exactly those graphs $X$ in the category of simple graphs with an homomorphism to the complete graph $K_n$. Question 1: Are there other ...
0
votes
1answer
28 views

Order embedding and graph embedding of Hasse digraphs

If there is an order embedding from order A to order B, is there a graph embedding between their Hasse digraphs? What if we replace 'embedding' by 'order preserving' and 'homomorphism' etc?
2
votes
0answers
61 views

What are co-products for directed graphs?

I define a digraph as a set $V$ (vertexes) and a relation $E$ (edges) on $V$. Morphisms of digraph are functions which preserve $E$. So we have a category. What are co-products in this category? (I ...
1
vote
2answers
92 views

In a tree, is there always a sink where every longest path ends in?

Let $T$ be an undirected tree. Can we always find a leaf vertex $s$ such that every longest path of $T$ has its other endpoint in $s$? It's easy to see that every longest path passes through the ...
0
votes
1answer
52 views

graphs with specific radius and diameter

Can anybody help me in finding out the family of non-bipartite graphs where diameter is 2 and radius is 1. The only graphs that came into my mind are wheel graphs. Is there any other graph that I am ...
2
votes
1answer
57 views

Orienting planar graphs

What is the minimal $d\in \mathbb N$ for which every simple finite planar graph can be oriented in such a way that the out degree (i.e. the number of edges leaving a vertex) of every vertex is $\leq ...
2
votes
0answers
129 views

How to Enumerate of all simple connected labeled graphs with prescribed degree sequence?

For v=4 vertices, there must be 7 possible graphic sequence (3,3,3,3)(3,3,2,2)(3,2,2,1)(3,1,1,1)(2,2,2,2)(2,2,1,1)(1,1,1,1). From (3,3,3,3), one simple graph(complete) can be found. From(3,3,2,2), 6 ...
3
votes
1answer
124 views

Categorical characterization of complete graphs

In the category of (finite) simple graphs with graph homomorphisms $\mathsf{SimpGph}$, (how) can the complete graphs $K_n$ be characterized by genuinely categorical means? Are they somehow ...
6
votes
1answer
63 views

Graph chromatic number and graph homomorphism?

For two graphs G and H such that $\chi(G) < \chi(H)$, then is it true that there always exist a graph homomorphism from G to H ?
1
vote
1answer
390 views

Graph Theory: Graph with bipartite subgraph has MORE than e(G)/2 edges.

Show that every loopless graph G has a bipartite subgraph with more than e(G)/2 edges. Use induction on the number of vertices. Clearly if n(G) = 2, the hypothesis holds. But I am not sure how to ...
5
votes
1answer
121 views

Understanding Proof of Hopcroft & Karps Matching Algorithm

Hopcroft & Karps algorithm to compute a maximum matching takes $\mathcal O(mn^{1/2})$ time, which is composed by $\mathcal O(n^{1/2})$ iterations and each iteration taking $\mathcal O(m)$. In my ...
4
votes
1answer
643 views

Diameter of a Connected Graph

Problem Prove that if $G$ is connected and $\text{ diam}(G) \geq 3$, then $\overline{G}$ is connected. Prove that if $\text{ diam}(G) \geq 3$, then $\text{ diam}(\overline{G}) \leq 3.$ Prove that if ...
2
votes
1answer
54 views

Hamiltonian in graph theory [duplicate]

Show that if G is bipartite with bipartition (x,y) where |x| is not equal to |y|, then G is non-hamiltonian. Case 1. G is not connected (trivial) Case 2. G is connected Is it ok to start Letting C ...
1
vote
1answer
128 views

Complete graph invariant

Does anybody know whether the multiset of the determinants (possibly together with the order of the submatrix they refer to) of all the principal minors of the (symmetric) adjacency matrix of a graph ...
3
votes
4answers
4k views

Calculating number of edges from a degree sequence

Problem: Suppose a graph $G$ has degree sequence $25, 18, 18, 5, 2, 2$. How many edges are there in $G$? I am assuming since the definition of degrees of a vertex that each one of the 6 vertex's ...
0
votes
1answer
140 views

Show that simple and connected graph is forest if and only if every edge is cut edge

Given a simple and connected graph $G=(V,E)$, how can we show that $G$ is a forest if and only if every edge is a cut edge?
3
votes
0answers
162 views

Multivariable calculus: optimizing for shortest path along a curvy plane?

I want to write a computer program which can help me spend the least amount of energy and time walking between locations on my university campus. My campus is very hilly, and it is also extremely hot ...
0
votes
1answer
333 views

Checking for graph isomorphism by hand

I'm working through "A First Look at Graph Theory" by Clark & Holton, and in the first exercise, there are problems asking to check whether different graphs are isomorphic to each other. I find ...
1
vote
1answer
107 views

Arecthere any proofs and formula to count all simple labeled, connected isomorphic and non isomorphic connected simple graphs separately?

Number of Labeled graphs with n vertices are $2^{\binom{n}{2}}$. Number of connected labeled graphs with n vertices follows the following recuurence, $C_{n} = 2^{\binom{n}{2}} - ...
0
votes
1answer
404 views

reverse greedy algorithm

I got this reverse greedy algorithm here as below: First we sort edges of G in decreasing order, as e_1 > e_2 > ... e_m Then begin with T := G for i=1,2,...,m if T-e_i is connected, then T:= ...
0
votes
0answers
100 views

how to proof $S^{2n+1}$ can be decomposed to one 2n+1 complex and $S^{2n}$can be decomposed to two 2n complexes?

Is there any reference refer to the question? The fact is apparent ,but i can't proof it.
1
vote
1answer
1k views

Graph Theory / Networks … Triadic Closure and Strong/Weak Ties

Okay, so the problem I am working on is this: Consider the graph in the figure below, in which each edge — except the edge connecting B and C — is labeled as a strong tie (S) or a weak tie (W). ...
3
votes
1answer
427 views

Relation between articulation points and bridge edges

What is the relation ship between articulation points and bridges of a graph. Specifically, if there are no articulation points in a graph is it necessary that there will be no bridge edges.
1
vote
1answer
55 views

Number of strongly-connected digraphs

Is there a closed formula for the number of non-isomorphic strongly-connected digraphs on $n$ vertices?
3
votes
0answers
161 views

What can we say about two graphs if they have similar adjacency matrices?

Suppose we have two (finite, simple, undirected) graphs, what can we say about these graphs if they have similar adjacency matrices? Observations to begin with: If $G_1$ and $G_2$ are isomorphic, ...
1
vote
0answers
83 views

Expected distance traversed between 2 vertices on probabilistic graph

Let $V = \{1,2,3,...,N\}$ be the vertex set of a graph. Let $d(i,j)>=0$ represent the $(i,j)$ vertex distance between vertices $i$ and $j$, $i \in V, j \in V$. Now, define a non-negative number ...
1
vote
1answer
480 views

cut vertices of connected and non connected graphs

Prove that if $v$ is a cut-vertex of a connected graph $G$, then $v$ is NOT a cut vertex of $G'$. I know that a vertex $v$ is a cut vertex of $G$ IFF there exists vertices $u$ and $w$ $(u,w \not=v)$ ...
2
votes
1answer
664 views

Maximum value for V in planar self-complementary graph

Let G=(V,E) be a simple and self complementary graph. What is the maximum number of vertices it can have if both it and its complement are planar when i) G is connected? ii)G is not necessarily ...
1
vote
1answer
50 views

What is the way(s) to represent an embedding of a planar graph?

As we know there are some ways to state a graph such as: it's drawing, adjacency matrix and sets of vertices and edges. And we know planar graph contains one or more embeddings. My question is what ...
7
votes
1answer
183 views

A puzzle on gcd

Consider a directed graph whose nodes are positive integers. There is a directed edge from $a$ to $b$ if $a<b$ and $a$ is relatively prime to $b$, i.e. $\mathrm{gcd}(a,b)=1$. Given two integers ...
1
vote
1answer
145 views

Problem on strongly connected directed graph involving $\gcd$

Let $G=(V,E)$ be a strongly connected directed graph. Suppose that $p$ is the greatest common divisor of the lengths of cycle in $G$. How one can prove that there exists a partition $V_0,...,V_{p-1}$ ...
5
votes
2answers
146 views

Are there connected, planar graphs of size $N$ with minimal degree $\left( N−2 \right)$ for any $N \in \mathbb{N}$?

I was doing a bit of doodling today with graphs of N vertices, trying my best to make sure that every vertex had minimal degree of $\left( N-2 \right)$ without any crossings. I was able to form ...
0
votes
0answers
56 views

Expected size of the largest cycle

Assume that given $n$, a graph $G$ is created randomly, so that each point is directed to any of the $n$ points (including itself) at random. (So self loop is possible.) Then $G$ is graph of $n$ ...