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

1
vote
1answer
38 views

Is the triforce graph an sp-graph?

Consider the examples and the statements where a series-parallel graph (sp-graph) is defined inductively with respect to series composition and parallel composition of other sp-graphs or of $K_2$. ...
1
vote
1answer
26 views

Graph Theory Logic

So, I have this graph theory question saying that "A graph G had 6 vertices and their degrees are 2d,2d,2d+1,2d+1,2d+1 and 3d-1, show that d must be even using the sum of the edges." Now it obviously ...
1
vote
1answer
38 views

prove that if every induced subgraph of G is connected,then G is the complete graph Kn [closed]

Let G be a graph of order n prove that if every induced subgraph of G is connected,then G is the complete graph Kn
1
vote
1answer
14 views

Number of Plane Oriented Recursive Trees

The number of plane oriented recursive trees is $(2n-3)!!$ I understand that given a vertex $v$ with $k$ successors, there are $k+1$ ways to attach a new vertex to create a new tree of size one ...
1
vote
1answer
49 views

Efficient way to show Graph is a tree in proof

I am new to inductive proofs in general, and brand new to graph proofs. I am looking for an efficient way to declare that the induced subgraph prior to application of induction is, in fact, a tree. ...
1
vote
1answer
52 views

Graph and its complement that both contain Eulerian circuits

Find a graph $G$ on $7$ vertices such that both $G$ and $\overline G$ contain Eulerian circuits. $\bar G$ means complementary graph. Graph is called Eulerian circuit if the trail is closed. Please ...
1
vote
1answer
39 views

Prove $\forall$ graphs, $\alpha(G) \ge \frac{n}{\Delta(G)+1}$

Prove $\forall$ graphs, $\alpha(G) \ge \frac{n}{\Delta(G)+1}$ where $\alpha(G) :=$ maximum independent set; $\Delta(G) :=$ is the maximum degree of any vertex and $n$ is the total number of vertices. ...
1
vote
2answers
56 views

Verbal Explanation of Math Notation

I am looking at a definition for an induced subgraph. I completely understand what an induced subgraph is, so an explanation of that is beside the point. What I am really interested in is a ...
1
vote
3answers
36 views

Can a graph be strongly and weakly connected?

I'm currently revising course notes on directed graphs. It says that a directed graph (digraph) is strongly connected if there is a path between every pair of vertices. It also says that a digraph ...
1
vote
1answer
31 views

Representative System for Graph Cycles

Let $G$ be a graph containing precisely $n$ copies of $C_r$, where $n\geq 1$, $r\geq 3$, and no other cycles. Under what conditions on $n, r$ does there exist a subgraph $H\subseteq G$ that shares ...
1
vote
1answer
36 views

Is there a nontrivial perfect vertex transitive graph?

Where would one find a nontrivial (i.e. not complete multipartite) graph who is both vertex-transitive and perfect? Is there one? Edit: Perhaps I should add: apart from even cycles?
1
vote
1answer
27 views

Show that $c(G)\geq |V|-|E|$, where the equality holds iff $G$ is cycless.

Let $c(G)$ denote the number of connected components of a graph $G$. I am asked Let $G=(V,E)$. Show that $c(G)\geq |V|-|E|$, where the equality holds iff $G$ is cycless. If I'm understanding ...
1
vote
1answer
36 views

Drawing a simple graph with six vertices and varying degrees

I am attempting to solve the following problem. I have to draw a graph having the given properties or explain why no such graph exists. The conditions I am given are that it is a simple graph; with ...
1
vote
1answer
86 views

Coloring/Labelling problem in Polynomial reduction of Isomorphism

** Question :** Notice the inequality inside yellow box. If $i_1$ has $n$ possible vertex, then $j$ has maximum $(n-1)$ vertices. For $\mu_{i_1,j}$ , it should be $1\leq j \leq (n-1)$ . but it is ...
1
vote
1answer
23 views

Why is $0$ an eigen value of $L_G$?

I am learning Spectral Graph Theory. If the Laplacian Matrix of a graph $G=(V,E)$ is defined by $(a_{ij})=-1 ;(i,j)\in E, d_i ; i=j$ and $0$ otherwise then how does it follow that $0$ is an ...
1
vote
1answer
39 views

Spectrum of k-partite graph

For a given undirected graph, it is known that the signless Laplacian $Q=D+W$ is positive semidefinite, where $W$ is the adjacency matrix and $D$ is the degree matrix. In particular, the smallest ...
1
vote
2answers
51 views

Connecting up boxes mathematically (Puzzle)

How would you connect each black box once to each colored box without any lines overlapping, this is racking my brain so please help. Note that you can move the boxes where ever you want. Maybe ...
1
vote
1answer
29 views

Number of cycles of length 4 in K7

The answer to this I believe is $1/2$ * $7C3$ * $3!$ How do you arrive to this answer? I understand the $1/2$ since the graph is undirected, but nothing else. Isn't there 4 ways to choose a cycle of ...
1
vote
1answer
22 views

Add one edge to the graph such that the graph will not be 3-colourable

Could you guys help me solve this example? The question is, whether it is possible to add one new edge such that the resulting graph is not 3-colourable and prove it. I was trying to find a way to ...
1
vote
1answer
29 views

Proving in planar graph

So I have a connected triangle-free planar graph - let's name it G. So I have proven that there exists a vertex V $$deg(V)\leq 3$$ I proved that using $$m\leq 3n-6$$ where $$n=|V(G)| , m=E(G)$$ along ...
1
vote
1answer
33 views

Show that K and K' cannot both contain an Eulerian trail

For question (b), I understand how to prove that they can't both contain an Eulerian trail--eulerian trail exists if and only if there are no more than 2 odd degrees of the vertices. So for a ...
1
vote
1answer
16 views

Is there any real application of Max-Tolerance Graphs, Interval Graphs?

I have read one article about Max-Tolerance Graph:. Basically: Max-tolerance graphs can be regarded as generalized interval graphs, where two intervals $I_i$ and $I_j$ induce an edge in the ...
1
vote
1answer
54 views

Can a simple undirected graph with 11 vertices and 53 edges have a Eulerian circuit?

I have gathered these but I can't connect them properly. The sum of the degrees of the vertices is 106. So d1+d2+d3+d4+d5+d6+d7+d8+d9+d10+d11=106 To have a eulerian circuit no vertex must have an odd ...
1
vote
2answers
65 views

The maximum number of girls you can accommodate in a row

I was playing around with the following problem: 'What is the maximum number of girls in a group of boys and girls that can be seated in a row of $x$ seats so that no $n$ girls are sat next to each ...
1
vote
1answer
33 views

Maximum number of edges of a planar graph without cycles of length 3 and 4

I'm trying to calculate the maximum number of edges in a planar graph without cycles of length $3$ and $4$ (thus, $C_3$ and $C_4$). I've assumed that the condition is that the length of each face has ...
1
vote
2answers
61 views

Maximizing the sum of the products of endpoints of edges in a graph

Let $G$ be a graph with vertex set $V=\{v_1,v_2\dots v_n\}$ and edge set $E$. Let $f:V\rightarrow \mathbb [0,\infty)$ be a real valued function such that $\sum\limits_{i=1}^n f(v_i)=A$. What is the ...
1
vote
2answers
24 views

How do I properly construct a graph from an adjacency matrix?

I understand that an adjacency matrix shows connectivity between vertices but I don't get how to properly construct the graph from them. In one of my lectures I was given this adjacency matrix: ...
1
vote
1answer
35 views

The number of spanning trees of $W_4$

I need to find the number of spanning trees of $W_4$ (wheels with 5 vertices), can anyone tell me how ? I guess that the number of spanning trees is 45 spanning trees. I'm not sure how to get this. I ...
1
vote
1answer
41 views

Proof $K_3,_n$ is $n^2 3^{n-1}$

The number of spanning trees of $K_3,_n$ is $n^2 3^{n-1}$, this is true if we try by induction for any $n$ ( with n = 4, 5, . . .). is it true ?? How to prove $K_3,_n$ is $n^2 3^{n-1}$ ??
1
vote
1answer
67 views

How to algorithmically calculate the adjacency matrix of platonic solids

I need to devise a algorithm (in Python) that calculates adjacency matrices for the platonic solids. The input into the algorithm needs to be the number of polygons meeting at each vertex and the ...
1
vote
1answer
82 views

Number of distinct cycle in complete undirected graph of length $4$?

Let $G$ be a complete undirected graph on $6$ vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length $4$ in $G$ is equal to $15$ $30$ $90$ $360$ My attempt : ...
1
vote
2answers
72 views

Graph theory, graph coloring, hamilton

A simple graph G has $14$ vertices and $85$ edges. Show that G must have a Hamilton circuit but does not have an Euler circuit. My attempt: to be hamilton circuit, each should have degree at least ...
1
vote
1answer
280 views

All Ihara $\zeta$ functions for planar $k$-regular graphs with a given set of faces are equivalent

This sounds like a simple piece of math (which got a long story over time, thanks for reading!) and the consequence seems surprising. At least to me. Here it is: It boils down to comparing two ...
1
vote
1answer
35 views

Star graph second-smallest eigenvalue

Prove that the star graph $K_{1,n-1}$ on $n$ vertices has $\lambda_2 = 1$, where $\lambda_2$ is the second-smallest eigenvalue of its' Laplacian. Is it true for all trees?
1
vote
1answer
49 views

Prove that a simple graph with $2n$ vertices and $n^2 +1$ edges contains a triangle for $n \ge 2$

Prove that a simple graph $G$ with $2n$ vertices and $n^2 +1$ edges contains a triangle for $n \ge 2$. I see it for $n = 2$ or $n = 3$ ... , but I fail to generalize it.
1
vote
2answers
50 views

How many trees are there on 7 vertices, where vertices 2 and 3 have degree 3, 5 has degree 2, and all others have degree 1?

How many trees are there on 7 vertices, where vertices 2 and 3 have degree 3, 5 has degree 2, and all others have degree 1? So far, I am able to determine that vertices 1, 4, 6, and 7 are leaves. My ...
1
vote
1answer
24 views

How do i prove that there are at least 12 faces of degree 5 for a regular graph of degree 3 where there are no faces of degree less than five,

how would i go about proving this? Using the handshaking lemma, the sum of the vertex degrees = 2m. So, we have $3n = 2m$. Using Euler's Formula : $n-m+f = 2, $ we have $\frac{2}{3}m - m +f = 2$ ...
1
vote
2answers
54 views

Induction: Every connected graph has a spanning tree

Definition A spanning tree of a graph $G$ is a tree $T\subseteq G$, with $V_T=V_G$ Question Proof, by induction, that every connected graph $G$ with $n$ vertices contains a spanning tree. ...
1
vote
1answer
23 views

Number of all possible orientations in a graph

What is the number of all possible orientations for an undirected graph? I think it must be $2^{|E|}$, because we have $|E|$ edges, each of them can have 2 choices for it's direction. Is it true?
1
vote
2answers
101 views

Prove that every strongly connected digraph has an odd directed cycle if its underlying graph has an odd cycle

Let D be a strongly connected digraph. Prove that if its underlying graph has an odd cycle, then D has an odd directed cycle. My first approach would be to assume that D has not such a cycle and then ...
1
vote
2answers
23 views

Is the hypercube the only connected, regular, bipartite simple finite graph?

Suppose we know that a simple graph (no multiedges or loops) with finitely many vertices is connected, regular (every vertex has the same degree), and bipartite. Must the graph be a hypercube or an ...
1
vote
1answer
37 views

How can classical random graph theory be applied to real world networks?

In real world networks, we have no further information about the structure of the networks. For example, in the Facebook network, we assume each one has some known particular probabilities to ...
1
vote
1answer
27 views

Proof that Laplacian spectrum is symmetric for bipartite graphs

Proposition. If $G$ is a bipartite graph with at least one edge, then its spectrum is symmetrical with respect to $0$, i.e. if a number $\lambda$ is an eigenvalue of $G$ then $- \lambda$ is also an ...
1
vote
1answer
61 views

Given a simple graph with $n = 4k + 2$ vertices. Can the vertices of this graph have distinct degrees?

So I was given this question that asks: Given a simple graph with $n = 4k + 2$ vertices. Can the vertices of this graph have distinct degrees? I was wondering how I would go about this. I am usually ...
1
vote
1answer
56 views

Proof that graphs are not isomorphic

If two graphs are isomorphic, they must have: the same number of vertices the same number of edges the same degrees for corresponding vertices the same number of connected components I know ...
1
vote
1answer
27 views

Using Euler's theorem to calculate the number of edges in a graph

I want to use Euler’s theorem for planar graphs to proof that for a tree $T = (V, E)$ that $|V | = |E| + 1$. Now It's very obvious that a tree is a planar graph since it is connected and there is no ...
1
vote
1answer
221 views

The number of pendant vertices in a tree

Let $T$ be a tree with vertices $\{v_1, v_2, . . . , v_n \}$ for $n \geq 2$. Prove that the number of pendant vertices in $T$ is equal to $$\large{2 + \sum_{v_i,deg(v_i) \geq 3}\big( deg(v_i) - 2 ...
1
vote
1answer
91 views

What does Ramsey theory tell us?

I have recently started reading about Ramsey theory, though I'm a bit confused about what does it actually tell us. As long as I understood, it says that in a big enough complete graph one can find a ...
1
vote
2answers
50 views

Separating points on the n-sphere

Consider an unweighted and undirected graph $G=(V,E)$, where the vertices $V$ of $G$ lie on the unit n-sphere. If we choose a normal vector uniformly at random on this $n$-sphere, then the ...
1
vote
1answer
16 views

Prove that Graph $(V \cup W,E^{\prime})$ is connected

Suppose $(V,E)$ is a connected undirected graph, in which $V = \{v_1, v_2,..... , v_n\}$. Let $W = \{w_1,w_2,.....,w_n\}$. How can I prove that the undirected graph $(V \cup W,E^{\prime})$ is ...